프로그래머스 광물 캐기 문제 풀이(Python, Greedy, Lv2)

프로그래머스 광물 캐기 문제 바로가기

문제 접근

음 보고 생각을 좀 했던 문제이다.
내가 푼 풀이는 아래와 같다. 다른 사람들은 다르게 풀었을 수도 있을 것 같다.

1. 광물의 개수가 30까지밖에 없기때문에 모든 광물을 5로 끊어서 각각 다이아, 철, 돌로 캤을 때의 피로도를 구하고 이를 테이블에 저장한다.
2. 그 후 테이블을 정렬한다. 정렬 순서는 돌을 기준으로 정렬한다.
   같은 광물 5개를 캐고 그 피로도를 합한것이기 때문에 무조건 돌의 피로도가 가장 높고 돌로 정렬했을 때 철로도 정렬됨을 알 수 있다.
3. 가지고 있는 곡갱이는 다이아, 철, 돌 순서로 사용한다.
4. 총 피로도를 return한다.

문제 풀이

테이블 생성하고 값 넣기

5개로 끊어서 테이블에 값을 넣는다. 이로서 하나의 dp[0]에는 5개의 광물을 캤을 때 다이아, 철, 돌로 캔 피로도가 다 들어간다.

def digging(start):
        i = 5
        while minerals and i > 0:
            mineral = minerals.pop()
            dp[start][0] += 1
            if mineral == "diamond":
                dp[start][1] += 5
                dp[start][2] += 25 # 돌로캐면
            elif mineral == "iron":
                dp[start][1] += 1 # 철로 캐면
                dp[start][2] += 5 # 돌로 캐면
            elif mineral == "stone":
                dp[start][1] += 1
                dp[start][2] += 1
            i -= 1
        return

정렬하기

돌을 기준으로 정렬해준다.

dp.sort(key = lambda x: (-x[2],-x[1],-x[0]))

다이아, 철, 돌 순으로 곡갱이 사용해서 피로도 구하기

이렇게 정렬한 피로도들을 결국에는 하나씩 뽑아서 더해야 한다. 이렇게 할 경우에 나올 수 있는 경우의 수는 다이아 곡갱이만 사용하는 것이 가장 적은 피로도를 가질 것이다.
하지만 우리는 한정된 다이아 곡갱이를 가지고 있으므로 돌곡갱이로 캤을때 피로도가 가장 높은 녀석부터 다이아 곡갱이로 캔다. 그것을 위해 정렬한 것이다.

이렇게 다이아로 다 캤으면 철로, 그 다음에 돌로 캐준다.
그렇게 해서 다 더한 합이 최소 피로도이다.

start = 0
    for i in range(3):
        pick = picks[i]
        while pick > 0 and start < len(dp):
            answer += dp[start][i]
            start += 1
            pick -= 1

제출 코드

def solution(picks, minerals):
    answer = 0
    # 곡갱이 1 = 5광물
    # 곡갱이 하나 시작하면 깨질때까지 사용해야함
    # 광물은 주어진 순서 => queue or stack
    # 종료 조건 => 모든 광물 캐기, 모든 곡갱이 사용
    
    # 최소한의 피로도를 return
    minerals.reverse()
    dp = [[0 for i in range(3)] for j in range(min(len(minerals)//5 + 1, sum(picks)))]
    def digging(start):
        i = 5
        while minerals and i > 0:
            mineral = minerals.pop()
            dp[start][0] += 1
            if mineral == "diamond":
                dp[start][1] += 5
                dp[start][2] += 25 # 돌로캐면
            elif mineral == "iron":
                dp[start][1] += 1 # 철로 캐면
                dp[start][2] += 5 # 돌로 캐면
            elif mineral == "stone":
                dp[start][1] += 1
                dp[start][2] += 1
            i -= 1
        return
    N = len(minerals)
    for i in range(sum(picks)):
        digging(i)
    # 광물 피로도 표
    # 가장 적은 피로도 루트를 구하면 됨
    # 다이아부터 선택 greedy
    dp.sort(key = lambda x: (-x[2],-x[1],-x[0]))
    start = 0
    for i in range(3):
        pick = picks[i]
        while pick > 0 and start < len(dp):
            answer += dp[start][i]
            start += 1
            pick -= 1
    return answer