백준 1149번 (동적 프로그래밍)

해왔던대로 단계적으로 모아가는 알고리즘을 짰다.

이 코드를 예제를 돌려보자.

26, 40, 83

49, 60, 57

13, 89, 99

 

12번줄 반복문을 한번 돌려본다.

26, 40, 83

40+49(89), 26+60(86), 26+57(83)

13, 89, 99

 

끝까지 돌려본다.

26, 40, 83

40+49, 26+60, 26+57

26+57+13, 26+57+89, 26+60+99

 

L[2]중 최솟값인 26+57+13이 정답이 된다.

 

쉽게 말하자면, L[i][0]이란, i번째에 빨간색을 골랐을 때, 0부터 i까지 골라서 어떤 색깔을 골라 나올 수 있는 최솟값이 된다.

같은 방식으로 L[i][1], L[i][2]에는 i번째에 초록색을 골랐을 때의 최소, 파란색을 골랐을 때의 최소가 들어오게 된다.

그리고 이 반복문을 N까지 돌리게 되면 L[N-1][0], L[N-1][1], L[N-1][2]에는 N-1에 빨간색, 초록색, 파란색을 골랐을 때의 각각의 최선의 수가 들어가게 되고, 이 중 최솟값을 구하면 전체의 최선의 수가 나오게 된다.

 

이번에도 단계적으로 점차 커져가게 만들어 결국 전체까지 가서 답을 구하게 되는 알고리즘을 공부해보았다.