https://www.acmicpc.net/problem/1149
1149번: RGB거리
첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나
www.acmicpc.net
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에 각각 더해지는 값의 최솟값을 넣게 되면, 자연스럽게 그 경우의 최솟값을 구할 수 있게 된다.
'알고리즘 > 백준 문제풀이' 카테고리의 다른 글
[백준] 11718번 : 그대로 출력하기 (python 파이썬) [입력 횟수가 정해지지 않을 때] (0) | 2022.12.24 |
---|---|
[백준] 5430번 : AC (python 파이썬) (0) | 2022.06.04 |
[백준] 1074번 : Z (python 파이썬) (0) | 2022.05.08 |
[백준] 10026번 : 적록색약 (python 파이썬) (0) | 2022.04.16 |
[백준] 1655번 : 가운데를 말해요 (python 파이썬) (0) | 2022.04.01 |