백준 1149번 파이썬

 

1149번: RGB거리

이번달까지는 dp만 풀 것 같다. 오늘은 가야할 곳이 있어서 바쁜 나머지,, 잠도 요즘 덜자고? 맘도 급했고 문제가 잘 풀리지 않았다.ㅠ

dp인것은 대충 감이 오지만, dp는 지금까지 백준에서는 1 또는 2차원 배열을 이용해서 차곡차곡 이전의 요구사항에 맞게 정답을 만들어 나갔다. 예를들어 최솟값을 찾는 거라면, n이 될 때까지, 점화식을 이용해서 1 ~ n 까지 차례대로 차곡차곡 이전의 값을 이용해서 n일때의 최솟값을 만들어 나가는 느낌이다.

이 문제도 그렇다.! 배열을 최대한 이용하는 것이 시간 효율이 좋다. 

코드

n = int(input())
dp = []

for i in range(n):
    dp.append(list(map(int,input().split())))

for i in range(1, n):
    dp[i][0] = dp[i][0] + min(dp[i - 1][1], dp[i - 1][2])
    dp[i][1] = dp[i][1] + min(dp[i - 1][0], dp[i - 1][2])
    dp[i][2] = dp[i][2] + min(dp[i - 1][0], dp[i - 1][1])
print(min(dp[n-1][0],dp[n-1][1],dp[n-1][2]))

풀이

문제의 조건을 인지하고 난 뒤,

예시로 n이 2인 아래와 같은 경우를 보자

	dp[i][0] => 빨강	dp[i][1] => 초록	dp[i][2] => 파랑
dp[0]	1	1	100
dp[1]	2	5	100

이때, 우리는 최소 비용이 중복될 수 있다는 것을 알 수 있는데, 이 중복된 색을 어떤 것을 선택하느냐 그 뒤의 색들을 선택해서 최솟값이 결정된다. for문 3번 돌리지 말고, 배열의 index 기능을 활용하자.

// 2 번째 집이 빨강색을 선택했을 때, 이 때 까지의 최소비용

dp[1][0] = dp[1][0] + min(dp[1][1] , dp[1][2]) => 여기서 min은 이전 집에서 칠한 색 제외한 색 중 비용이 적은 것 고르는 과정.

// 초록색 선택 일때 최소비용

dp[1][1] = dp[1][1] + min(dp[1][0] , dp[1][2])

// 파란색 선택 일때 최소비용

dp[1][2] = dp[1][2] + min(dp[1][0] , dp[1][1])

이런식으로 n까지 dp에 값을 저장해나가서 dp[n-1] 의 값들 중 min 인 값이 정답이 되는 것이다.

 

참고자료

[백준] 1149번(python 파이썬)