[백준] 1149 - RGB거리

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

1149번: RGB거리

문제 한줄 이해

-N개의 집이 있을때 문제에 주어진 규칙에 따라 집에 색칠을 칠할때 최소비용 구하기!

 

생각난 풀이

1번째 방법: 처음에는 첫번째 집이 각각 R, G, B의 경우에 따라 모든 경우의 수를 재귀함수를 통해 구현했다.

import sys
n = int(sys.stdin.readline())
homes = []
for i in range(n):
    homes.append(list(map(int,sys.stdin.readline().split())))

def back(start,cnt,result):
    global ans
    if cnt == n:
        if ans > result:
            ans = result
        return
    for i in range(3):
        if i != start and result < ans:
            back(i,cnt+1,homes[cnt][i]+result)
            
for i in range(3):
    back(i,0,0)
print(ans)

하지만 50퍼까지는 오르고 시간초과,,, 원인은 코드상 시간복잡도가 3^n-1이라 최악의 경우 엄청난 연산을 하게 된다.....

 

2번째 방법: 방법이 떠오르지 않아 우선 알고리즘 분류를 확인했다.

다름 아닌 다이나믹 프로그래밍 그래서 최대한 점화식의 규칙성을 찾으려고 노력했다. 

각각 R G B의 경우를 나눠서 확인 해줘야 하는건 분명했다. 

다이나믹 프로그래밍은 아이디어를 떠올리는게 쉽지 않은거 같다. 계속 연습해야겠다.