광물 캐기 C++ 분석

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

프로그래머스

문제의 조건을 확인

곡갱이 종류별로 5개, 미네랄 50개

 

생각할만한 방법

제일 완벽하고 만능인 방법이 뭘까, 모든 방법을 탐색하고, 최적의 값을 가져오면 된다.

 

주먹구구식으로 값 찾기

모든 방법을 탐색하는 데 탐색을 몇 번 해야하나? 곡갱이가 총 15개이기에, 곡갱이를 총 곡갱이를 모든 조합을 구한다면 15!이 되고, 이는 1e9를 넘어간다.

 

문제의 조건 확인하기

문제의 조건에서 미네랄이 총 50개이고, 곡갱이가 5번씩 사용 가니, 총 미네랄을 10개의 묶음을 만들 수 있다.

10개의 묶음 그러니까 곡갱이를 15개 중 최대 10개 밖에 못 쓴다.

이는 결국 15C10이다. 이를 계산하면 다음과 같다. 3,003이다.

 

충분히 완전 탐색으로 구할 수 있는 수이다.

그래서 다른 사람들의 코드를 확인한다면, dfs로 탐색하는 것이다.

 

다른 방법은?

조합을 생각하지 못하고, 다른 방법을 생각하더라도 해볼 수 있는 수는 하나 더 있다.

그리디다. 광물을 5개씩 묶음으로 만들고 이를 광물의 가치에 따라 내림차순으로 정렬하면 된다.

그리고 가치가 높은 다이아 곡갱이부터 광물을 캐면 된다.

 

이 방법이 되는 이유는 곡갱이의 순서가 고정이 되고, 광물의 순서를 변경해서 최소를 구할 수 있기 때문이다.

이를 증명하려면 그리디 정당성을 증명해야 하는데 솔직히 말해서 잘 모른다.

 

고려해야 부분이 하나 더 있는데, 광물의 가치를 어떻게 판단하느냐이다.

가치를 하나의 값으로 관리를 하거나, 직접적으로 광물의 수를 기록하는 방법이 있다.

이때 돌 5개가 철 1개보다 가치가 낮음을 알아야 한다.

그렇기 때문에 정렬 시 무조건 가치가 돌이 하나라도 더 많으면 앞으로 와야한다.

이를 광물의 수로 정렬 시 정렬 함수를 광물의 보유 수로 하나씩 비교해서 해야 한다.

하지만 광물의 수를 기록하지 말고 하나의 가치로 합산하는 방법으로도 가능하다.

돌이 1, 총 5개의 값은 5임으로 철은 6이면 된다.

이런 방식으로 돌 1, 철 6, 다이아 31로 가치를 합산해서 하나의 값으로 내림차순 정렬을 해도 된다.

 

나중에 그리디 정당성 증명을 잘 알게 된다면 추가적인 글을 작성하지 않을까 싶다.