프로그래머스. 광물 캐기

https://school.programmers.co.kr/learn/courses/30/lessons/172927#

프로그래머스

 

광물은 순서대로 캐야하고, 곡괭이는 한 번 쓰면 부서질때까지 써야 하기 때문에 광물들을 다섯개씩 그룹으로 나눈다.

 

그리고 각 그룹마다 우선순위를 부여한 후에, 우선순위가 높은 그룹부터 다이아 -> 철 -> 돌 곡괭이를 부여하면 된다.

 

우선순위는 표처럼 다이아는 25점, 철은 5점, 돌은 1점으로 부여한다.

 

이 문제에서 함정이라 할 수 있는 곳은 곡괭이의 수가 적어서 광물을 다 못 캘 수도 있다는 점이다.

 

광물은 무조건 주어진 순서대로 캐야하기 때문에, 그룹에 우선순위를 부여하고 곡괭이를 부여할때 만약 해당 그룹이 곡괭이를 다 써도 도달하지 못하는 순서에 있다면 제외해야 한다.

 

 

 

 

 

---

곡괭이의 총 갯수가 15개로 brute force, dfs 로는 시간초과지 않을까 했는데 dfs 로도 된다.

 

 

 

 

---

2023.09.23

 

다시 풀어봤다.

내가 이전에 순열에 대해 조금 햇갈렸는데, 예를들어 곡괭이가 최대갯수인 15개가 있으면 15! 의 경우의수가 나오는게 아닌가 생각했다.

 

실제로 만약 dfs 로 순수 순열을 구하면 15! 개가 나오겠지만, 생각해보면 그 중에는 중복되는 경우가 대부분이다.

예를들어 {0 0 1 1 2 2} 의 다음 순열도 똑같이 {0 0 1 1 2 2} 가 된다. 

따라서 중복을 제거하면 15! 보다 훨씬 적은 경우의수가 나온다.

c++ 의 next_permutation 은 중복을 제거하기 때문에 next_permutation 을 쓰면된다.