[백준 BOJ_1149] RGB거리 Python 풀이

출처: 백준 온라인 저지

문제Permalink

풀이Permalink

문제에서 주어진 규칙이 언뜻 보기에는 어려워보이지만 결국 같은 색의 집이 연속해서 칠해지면 안된다는 뜻입니다.

• Red Green Green (X)
• Red Green Blue (O)
• Red Green Red (O)

그러므로 i번째의 집은 i-1번째의 집과는 다른 색으로만 칠하면 됩니다.

동적계획법으로 풀어보겠습니다. 집을 칠하는 세가지 색의 비용을 담은 costs는 예시 input일 경우에는 다음과 같습니다.

# costs[house-1][color]
# color -> 0(Red) 1(Green) 2(Blue)
[ [26, 40, 83],
  [49, 60, 57],
  [13, 89, 99]]

다음은 cache인데 format은 costs와 같습니다. 다만 담아주는 값은 해당 색깔을 선택했을 때 최소비용을 담아줍니다.

1번째 집(i=0)은 costs와 동일하게 초기화 해준 뒤, for loop을 1(2번째 집)부터 N까지 돌려주며 각 색의 해당 비용(costs[i][color#])와 다른 두 색의 이전 집(i-1)의 최소비용 중 적은 것을 선택해 더해준 값을 저장해줍니다.

마지막으로 마지막 집(cache[N-1])의 최소비용 중 가장 적은 것을 골라 출력해줍니다.

코드Permalink

N = int(input())
costs = [ list(map(int, input().split())) for _ in range(N) ]
cache = [[0 for _ in range(3)] for _ in range(1000)]
cache[0][0] = costs[0][0]
cache[0][1] = costs[0][1]
cache[0][2] = costs[0][2]

for i in range(1, N):
    cache[i][0] = costs[i][0] + min(cache[i-1][1], cache[i-1][2])    
    cache[i][1] = costs[i][1] + min(cache[i-1][0], cache[i-1][2])    
    cache[i][2] = costs[i][2] + min(cache[i-1][0], cache[i-1][1])   

print(min(cache[N-1]))