알고리즘/백준 문제풀이
[백준] 1149번 : RGB거리 (python 파이썬)
매일_공부
2022. 5. 10. 22:38
반응형
https://www.acmicpc.net/problem/1149
import sys
n = int(sys.stdin.readline())
dp = [[0 for i in range(n)],[0 for i in range(n)],[0 for i in range(n)]]
for i in range(n):
r,g,b = map(int, sys.stdin.readline().rstrip().split(" ")) # r,b,g 입력
if i == 0: # 처음 입력 받을 때 (dp초기 입력)
dp[0][i] = r
dp[1][i] = g
dp[2][i] = b
else:
dp[0][i] = min(r+dp[1][i-1], r+dp[2][i-1]) # (r의 경우) 입력받은 r과 지난 b의 합과 입력받은 r과 지난 g의 합 비교하고 작은 값 집어넣기
dp[1][i] = min(g+dp[0][i-1], g+dp[2][i-1]) # (g의 경우) 입력받은 g와 지난 r의 합과 입력받은 g와 지난 b의 합 비교하고 작은 값 집어넣기
dp[2][i] = min(b+dp[0][i-1], b+dp[1][i-1]) # (b의 경우) 입력받은 b와 지난 r의 합과 입력받은 b와 지난 g의 합 비교하고 작은 값 집어넣기
print(min(dp[0][-1],dp[1][-1],dp[2][-1])) # 값 출력
전형적인 dp문제 중 하나이다.
dp의 형태는 [ [] , [] , [] ] 이며, 각각의 리스트는 r,g,b 를 의미한다. (정확하게는 r로 시작했을 경우, g로 시작했을 경우, b로 시작했을 경우)
처음 r,g,b 를 입력 받을 때에는 dp에 아무것도 없기 때문에 순서에 맞춰 dp의 처음 인덱스에 집어넣는다
다음 r,g,b를 입력 받을 때부터는
dp[i][0](r의 경우) 은 가능한 경우가 dp[i-1][1]에서 r을 더한 경우와, dp[i-1][2]에서 r을 더한 경우이다.
dp[i][1](g의 경우) 은 가능한 경우가 dp[i-1][0]에서 g을 더한 경우와, dp[i-1][2]에서 g을 더한 경우이다.
dp[i][2](b의 경우) 은 가능한 경우가 dp[i-1][0]에서 b을 더한 경우와, dp[i-1][1]에서 b을 더한 경우이다.
따라서 각각의 경우의 최솟값을 넣으면 된다,
문제 조건에서는 지난 번과 같은 색을 색칠할 수 없기 때문에, r의 경우는 지난 g와 b에서 올 수 밖에 없다.
따라서 dp에 각각 더해지는 값의 최솟값을 넣게 되면, 자연스럽게 그 경우의 최솟값을 구할 수 있게 된다.
반응형