돌다리 건너기
-
백준 2602번 돌다리 건너기 :: 마이구미알고리즘 풀이/동적계획법 2019. 11. 10. 23:18
이 글은 백준 알고리즘 문제 2063번 "돌다리 건너기" 를 풀이한다. 정올 고등부 문제이자, 동적계획법(DP) 문제이다. 문제 링크 - https://www.acmicpc.net/problem/2602 절대반지를 얻기 위하여 반지원정대가 출발한다. 원정대가 지나가야할 다리는 두 개의 인접한 돌다리로 구성되어 있다. 하나는 이고 다른 하나는 이다. 아래 그림 1은 길이가 6인 다리의 한 가지 모습을 보여준다. 그림에서 위의 가로줄은 를 표시하는 것이고, 아래의 가로줄은 를 표시한다. 두 돌다리의 길이는 항상 동일하며, 각 칸의 문자는 해당 돌에 새겨진 문자를 나타낸다. 두 다리에 새겨진 각 문자는 {R, I, N, G, S} 중 하나이다. 출발 R I N G S R 도착 G R G G N S 반지원정대가..