[백준 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보다 작거나 같은 자연수이다.

출력

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

---

풀이

RGB거리 문제와 마찬가지로 N번째까지의 최솟값을 담을 dp[N][0~2]을 선언해주고

dp[N][0] : N번째에서 빨강을 고를 경우의 최솟값

dp[N][1] : N번째에서 초록을 고를 경우의 최솟값

dp[N][2] : N번째에서 파랑을 고를 경우의 최솟값

으로 설정해준다

 

1번 집이 N번 집의 색과 같지 않아야 한다는 조건을 어떻게 해결할지 고민해보았고 다소 무식한 방법으로 해보기로 했다

dp_r : dp_r[0][0]을 -1000000으로 초기화하여 1번 집 선택을 빨강으로 강제한다

dp_g : dp_g[0][1]을 -1000000으로 초기화하여 1번 집 선택을 초록으로 강제한다

dp_b : dp_b[0][2]를 -1000000으로 초기화하여 1번 집 선택을 파랑으로 강제한다

dp_r.append([-1000000,g,b])
dp_g.append([r,-1000000,b])
dp_b.append([r,g,-1000000])

 

-1000000으로 초기화한 근거는 (N의 최댓값 * 집을 칠하는 최대비용)이다

dp_r,g,b[i][x]를 문제에서 제시하는 3번 조건에 맞도록 채워준다

dp_r,g,b[i][x] = min(dp_r,g,b[i-1][x를 포함하지 않는 2개의 값]) + A[i]     # 리스트 A[0~2]에는 N번째 r,g,b값들을 담는다

for i in range(1,N):
    A = list(map(int,sys.stdin.readline().split()))
    dp_r.append([min(dp_r[i-1][1],dp_r[i-1][2])+A[0],min(dp_r[i-1][0],dp_r[i-1][2])+A[1],min(dp_r[i-1][0],dp_r[i-1][1])+A[2]])
    dp_g.append([min(dp_g[i-1][1],dp_g[i-1][2])+A[0],min(dp_g[i-1][0],dp_g[i-1][2])+A[1],min(dp_g[i-1][0],dp_g[i-1][1])+A[2]])
    dp_b.append([min(dp_b[i-1][1],dp_b[i-1][2])+A[0],min(dp_b[i-1][0],dp_b[i-1][2])+A[1],min(dp_b[i-1][0],dp_b[i-1][1])+A[2]])

 

dp_r,g,b[N] 값에는 각각 1번집에서 r,g,b 선택이 강제된 최솟값들이 저장되어있을것이다

처음에 1번집의 r,g,b자리를 -1000000로 초기화했으니 dp_r,g,b[N]값들에 1000000+r,g,b를 더하여 돌려준다

dp_r[N-1] = list(map(lambda x:x+1000000+r, dp_r[N-1]))
dp_g[N-1] = list(map(lambda x:x+1000000+g, dp_g[N-1]))
dp_b[N-1] = list(map(lambda x:x+1000000+b, dp_b[N-1]))

 

첫 집과 마지막 집의 색이 다른 모든 값들 중 최솟값을 찾아준다

print(min(dp_r[N-1][1],dp_r[N-1][2],dp_g[N-1][0],dp_g[N-1][2],dp_b[N-1][0],dp_b[N-1][1]))