[코테 연습] RGB거리

문제

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

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

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

 

처음에 할당문제로 생각하고 헝가리안 알고리즘이 생각났다. 

 

https://algostudy.wordpress.com/2016/03/10/%ED%97%9D%EA%B0%80%EB%A6%AC%EC%95%88-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98/

헝가리안 알고리즘

근데 생각해보니 이건 X, Y가 같아서 정말 할당하는것뿐,,, 아니여따. 

 

이해한 바로 그림을 그려 설명해보쟈.. 난 그림그리는게 좋다... 알고리즘 예제로 주어진 걸로 그려보자

 

3

26 40 83
49 60 57
13 89 99

 

1차원적인 생각으로 첫번째 집을 가장 적은 비용으로 시작하면 다음과 같은 상황이 된다.  앞 뒤 집과의 색만 다르면 되니까, 바로 전에 선택되었던 집을 제외한 나머지 두 집 중 비용이 적은 집을 선택하면 된다.

 

예제만 보면 

1. 첫번째 집을 가장 적은 비용의 집을 고른다.
2. 바로 전 집의 색을 제외한 나머지 색상중 비용이 적은 색상을 고른다.
3. 2번째 과정을 집의 개수만큼 반복한다.

로 알고리즘을 짜면 되지만, 만약에 아래와 같은 상황이 된다면 첫 번째에 최소값을 고르는게 정답이 아닌것을 바로 알 수 있다. 

 

 

그래서 첫번째 집을 R과 G 그리고 B를 고르는 3가지 상황을 모두 고려해야한다. 

 

H[i][0] = min(H[i-1][1],H[i-1][2])+C[i][0] //R

H[i][1] = min(H[i-1][0],H[i-1][2])+C[i][1] //G

H[i][2] = min(H[i-1][0],H[i-1][1])+C[i][2] //B

 

그리고서 그중 가장 작았던 경우(R,G,B중)를 출력하면 끝!

 

n = int(input())

testN = []

for _ in range(n):
    testN.append(list(map(int, input().split())))

cost = [[0, 0, 0] for i in range(n)]

cost[0] = testN[0]

for i in range(len(testN)):
    cost[i][0]=min(cost[i-1][1], cost[i-1][2]) + testN[i][0] // r로 했을 때,
    cost[i][1]=min(cost[i-1][0], cost[i-1][2]) + testN[i][1] // g로 했을 때,
    cost[i][2]=min(cost[i-1][0], cost[i-1][1]) + testN[i][2] // b로 했을 때,

n -= 1

print(min(cost[n][0],cost[n][1],cost[n][2])) // 그 중에 제일 작은걸 고르기