백준 알고리즘 1149번

마찬가지로 문제를 풀기 전에 어떠한 알고리즘을 써야할지 생각을 해보자.

각 단계마다 경우의 수가 존재하고 그 경우의 수 중에 가장 최소값을 구하는 문제이다.

사용해야할 기법은 다이나믹 프로그래밍 !

단순하게 생각하자면 점화식은  [n - 1]의 최소값 + [n]의 최소값이다.

전 단계의 최소값과 지금 단계의 r,g,b 중 가장 작은 값을 더하는 것이다.

하지만 여기서 하나 더 생각해야되는 조건이 있다.

바로 전 단계의 r,g,b와 겹치면 안된다는 것이다. 내가 만약 r을 선택했다면 그 전 단계는 b, g중 최소 값을 더해야 된다는 뜻이다.

이 조건을 생각해서 다시 점화식을 세우면

min = Min([n - 1][g] + [n - 1][b]) + r 이 된다.

r,g,b 선택한 3가지 경우의 수중 제일 작은 값 하나만을 저장 하는 것이 아닌, b를 선택했을 경우, g를 선택했을 경우까지

모두 저장해주어야 한다. 

그 이유는 다음 단계를 위해서 이다. r, g, b 중 가장 작은 경우의 수 값만 저장한다면 그 다음단계에서는

전 단계에서 어떤 색을 선택했는지 알 수 있는 방법이 없다.

그래서 우리는 r, g, b 선택한 경우의 수를 모두 생각하며 dp를 진행해야한다.

위의 말을 정리해서 코드를 짜보면 다음과 같다.

n = int(input())
rgblist = []

for i in range(n):
    r, g, b = map(int, input().split(" "))
    rgblist.append([r, g, b])

dp = []

dp.append(rgblist[0])

for i in range(1, n):
    temp = []
    temp.append(min(dp[i-1][1], dp[i-1][2]) + rgblist[i][0]) // r을 선택했을 경우
    temp.append(min(dp[i-1][0], dp[i-1][2]) + rgblist[i][1]) // g를 선택했을 경우
    temp.append(min(dp[i-1][0], dp[i-1][1]) + rgblist[i][2]) // b를 선택했을 경우

    dp.append(temp)

print(min(dp[n - 1])) //  마지막 단계이므로 3가지 경우의 수 중 가장 작은 값을 리턴