[BOJ] 1149:RGB 거리 (Python)

문제 링크

https://www.acmicpc.net/submit/1149

풀이 전략

Dynamic Programming

각 입력값을 dp에 저장한다.

i번째 집을 빨강/초록/파랑으로 칠하는 경우를 나누어, 각각의 경우의 비용과 i-1번째까지의 집을 칠하는 비용의 합의 최솟값을 구한다.

위 단계의 값들 중 최솟값을 출력한다.

구현

if __name__ == "__main__":
    n = int(input())
    dp = []
    for _ in range(n):
        dp.append(list(map(int, input().split())))
    for i in range(1, n):
        # i번째 집을 빨강으로 칠할 때
        dp[i][0] = min(dp[i-1][1], dp[i-1][2])+dp[i][0]

        # i번째 집을 초록으로 칠할 때
        dp[i][1] = min(dp[i-1][0], dp[i-1][2])+dp[i][1]

        # i번째 집을 파랑으로 칠할 때
        dp[i][2] = min(dp[i-1][0], dp[i-1][1])+dp[i][2]

	# 최솟값 출력
    print(min(dp[n-1]))

복잡도

• Basic Operation: min, sum
• Time Complexity: $O(n)$

삽질

import operator

if __name__ == "__main__":
    n = int(input())
    arr = [0]*(n)
    past = None
    
    for i in range(n):
        r, g, b =  map(int, input().split())
        
        # tmp: 각 입력을 담는 dictionary
        tmp = {'r':r, 'g':g, 'b':b}
        
        # value를 기준으로 정렬
        sorted_tmp = sorted(tmp.items(), key=operator.itemgetter(1))
        
        # 만약 가장 작은 값의 key가 past와 다르다면
        if sorted_tmp[0][0] != past:
        # 값을 dp에 저장하고, 이 값에 대한 key를 새로운 past로 저장
            dp[i] = (sorted_tmp[0][1])
            past = sorted_tmp[0][0]
         
        # 만약 가장 각은 값의 key가 past와 같다면
        else:
        # 두 번째 작은 값을 dp에 저장하고, 이 값에 대한 key를 새로운 past로 저장
            dp[i] = (sorted_tmp[1][1])
            past = sorted_tmp[1][0]
            
    # arr의 값을 모두 더해 출력
    print(sum(arr))