[백준] RGB거리 2 17404번 (python) DP 무조건적인 선택

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

풀이 방법

dp에서 문제를 dp[i][j]를 i번째에 j색을 선택했을 때 최소 비용으로 설정했다.  ( 0<= j <= 2 0 == R, 1 == G, 2 ==B)

이렇게 설정 후 for 문을 1부터 N-1까지 돌며 각 경우에 대해 각 경우에 대해 

dp[i][0]일 땐 dp[i-1][1], dp[i-1][2] 중 작은 값을 선택

dp[i][1]일 땐 dp[i-1][0], dp[i-1][2] 중 작은 값을 선택

dp[i][2]일 땐 dp[i-1][1], dp[i-1][0] 중 작은 값을 선택 후 자신의 돈 더하기

위 과정을 해주면 된다. 

여기서 추가적으로 고려해야할 점은 처음과 끝이 다르게 선택되어야 한다는 점이다.

이를 위해 첫 선택을 강제하는 방법을 선택했다.

for 0~2까지 돌며 현재 선택된 색이 아닌 경우의 dp[0]값을 987654321처럼 큰 값을 할당하여 선택되지 않도록 했다.

또 마지막에서 시작 색과 다른 dp[N-1][j] j색을 선택해서 답을 구했다.

 

N = int(input())
money = [] ## 가격을 저장할 이차원 배열

for i in range(N):
    a, b, c = map(int, input().split())
    money.append([a, b, c])

ans = 987654321
for i in range(3): ## start를 선택했다. 선택을 강제하자
    dp = [[0, 0, 0] for _ in range(N)] ## dp[i][j] i번째에 j를 선택했을 때 최소 비용
    for j in range(3): ## i가 아닌 건 처음에 선택되지 않도록 큰 값으로 설정
        if i != j:
            dp[0][j] = 987654321        
    dp[0][i] = money[0][i] ## 0번째 i를 선택한 경우 돈을 설정
    for j in range(1, N): ## 3번 돌리기
        dp[j][0] = min(dp[j-1][1], dp[j-1][2]) + money[j][0]
        dp[j][1] = min(dp[j-1][0], dp[j-1][2]) + money[j][1]
        dp[j][2] = min(dp[j-1][0], dp[j-1][1]) + money[j][2]
    for j in range(3):
        if i != j:
            ans = min(ans, dp[N-1][j])

print(ans)