백준 1149, 17404 - 적록색약 1, 2 (Python)

dp문제. 그래프 탐색과 달리 최선의 선택을 계속 갱신해야 할 때 이용한다.

1149와 17404는 본질적으로 다르다. 끝까지 갱신을 하고 출력을 하면 되는, 즉 선형인 1149를 먼저 보자.

최솟값을 저장하는 dp에 나올 수 있는 최대 값보다 큰 inf를 설정해둔다.

이후 한번 앞부터 뒤까지 쭉 돌아서 dp를 갱신하고 최솟값을 출력한다.

​

17404는 출발점과 끝 점을 비교해야 한다는 점이 다르다. 즉 원형이다.

출발점과 끝 점이 다르면 비록 최솟값이라고 하더라도 이용할 수 없다.

그러니 출발점-끝점을 체크하는 방법을 이용하도록 한다.

이 방법의 핵심은, 출발 점이 총 3개, 도착점이 총 3개이니 출발-도착점의 경우의 수 9개를 2중 for문으로 돌면서 시작과 도착이 같은 경우는 갱신하지 않는 것이다.