백준 9461, 1149
1) 파도반 수열 (9461): https://www.acmicpc.net/problem/9461
삼각형들의 변의 길이를 차근차근 보면 규칙을 발견할 수 있다.
이것을 이용해 점화식 세우고 문제풀면 끝
P[i] = P[i-1] + P[i-5]
https://github.com/JangJuMan/2019-winter-PS/blob/master/DP/2_9461.cpp
2) RGB거리 (1149): https://www.acmicpc.net/problem/1149
어렵당.;;;
처음에 r, g, b를 선택하는 3가지 경우만 있다고 생각했는데
(왜냐면 그거만 선택하면 아래부터는 최소값 따라서 가니까 1 way인줄 알앗지;;)
만약 중간에 가서 cost가 같은 수가 나와버리면 거기서부터 프로그램이 헛돈다;;;
그래서 방향을 바꾸는 방법으로, 처음에 생각한게 위에서 아래 길을 결정하는 방법이었다면
이거는 아래의 cost를 전부 정리하면서 이전 결과값을 토대로 모든 경우를 다 확인하는 방법으로 했다.
cost라는 배열에 [0]:r / [1]:g / [2]:b 를 두고
이전 값을 통해 해당 값을 찾는 것.
예를들어 [0]: red를 알기 위해서는
이전 layer의 blue, green의 cost중 minimum을 가져오고, 그것에 입력값(red를 칠하는데 드는 cost(코드상에서는 rgb[0][i]에 해당)를 더한다.
https://github.com/JangJuMan/2019-winter-PS/blob/master/DP/2_1149.cpp
끗
ㅇㅁㅇ?!