[코딩 테스트 연습(파이썬/Python)] 백준 17404번(BOJ) _ RGB거리 2

https://www.acmicpc.net/problem/17404

17404번: RGB거리 2

[문제]

RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.

집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.

• 1번 집의 색은 2번, N번 집의 색과 같지 않아야 한다.
• N번 집의 색은 N-1번, 1번 집의 색과 같지 않아야 한다.
• i(2 ≤ i ≤ N-1)번 집의 색은 i-1, i+1번 집의 색과 같지 않아야 한다.

[입력]

첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.

[출력]

첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.

 

[아이디어]

1) RGB 거리 1번 문제와의 차이는 시작 집과 끝 집의 색이 달라야 한다는 것이다.

2) R,G,B로 시작할 때 각각을 구해줘야한다.

3) 1번 문제와 동일한 로직을 사용하되, 첫 시작을 R,G,B로 각각 강제하기 위해 dp의 첫 입력 줄을 조작해준다. 원하는 시작 자리만 제 값을 가져다 놓고, 나머지 자리에는 1000000보다 큰 임의의 값을 배치하면 첫 선택이 강제된다.

4) 마지막 결과에서 R로 시작했다면 R로 끝나는 것을, G로 시작했다면 G로 끝나는 것을, B로 시작했다면 B로 끝나는 것을 제외하고 최솟값을 구한다.

n=int(input())
rgb = [list(map(int,input().split())) for _ in range(n)]
ans = []
for i in range(3):
    dp=[[0,0,0] for _ in range(n+1)]
    dp[1] = [10000001]*3
    dp[1][i] = rgb[0][i]
    for k in range(2,n+1):
        dp[k] = [min(dp[k-1][1],dp[k-1][2])+rgb[k-1][0],min(dp[k-1][0],dp[k-1][2])+rgb[k-1][1],min(dp[k-1][0],dp[k-1][1])+rgb[k-1][2]]
    for k in range(3):
        if i!=k:
            ans.append(dp[-1][k])
print(min(ans))

R,G,B 시작 별로 for문을 돌리는게 아니라 한 번에 해결하고자 한다면 아래와 같이 코드를 구성할 수 있다.

n=int(input())
t = 100000001
dp=[[[0,0,0],[0,0,0],[0,0,0]] for _ in range(n)]
r,g,b = map(int, input().split())
x,y,z = map(int, input().split())
dp[1][0] = [t,g+x,b+x]
dp[1][1] = [r+y,t,b+y]
dp[1][2] = [r+z,g+z,t]
for k in range(2,n):
    a,b,c = map(int, input().split())
    dp[k][0] = [min(dp[k-1][1][i],dp[k-1][2][i])+a for i in range(3)]
    dp[k][1] = [min(dp[k-1][0][i],dp[k-1][2][i])+b for i in range(3)]
    dp[k][2] = [min(dp[k-1][0][i],dp[k-1][1][i])+c for i in range(3)]
for i in range(3):
    dp[-1][i][i] = t
print(min(map(min,dp[-1])))

3*3 dp로 각각 RGB 시작을 관리해주면 된다.