백준 12026번 BOJ거리 풀이/코드 (파이썬, 156ms) 다이나믹 프로그래밍!
코드만 궁금한 분은 깃허브링크 눌러주세요!
문제 설명
문제 해결 논리
다이나믹 프로그래밍이 항상 그렇듯, 변수 리스트 몇개 설정하고 적당히 잘 ..섞어서 풀면 된다. 나같은 경우에는
0. 처음문자부터 끝문자까지 각각 방문하는데에 필요한 최소에너지를 저장하는 리스트를 생성한다.
1. 우선 BOJ순서대로만 점프할 수 있으므로 딕셔너리에 J->O, O->B, B->J를 호출할 수 있게 키/값으로 저장해둔다.
2. 어떤 문자를 호출하는 경우 앞쪽의 모든 경우를 다 호출해야 하므로 B, O, J각각에 대해 visited 리스트를 만들어둔다. 가령 현재 O인 경우, 이전에 방문한 모든 B에 대해서 현재 O에 오는 경우의 에너지 값을 계산해야 하므로 이전에 방문햇던 B의 정보가 필요하다.
3. 앞쪽에서부터 지금 문자까지 올 수 있는 모든 경우에 대해 에너지를 계산하고 그중 가장 작은 값을 리스트에 저장하고 현재의 인덱스를 (현재 문자)_visited에 추가한다. 이 때, 에너지 계산 방식은 앞 문자까지 가는데에 필요한 에너지값 + (현재인덱스-이전 인덱스)의 제곱으로 계산된다.
3. 만약 방문하지 못하는 경우가 생기면 visited에 당연히 넣지 않고 sys.max값을 리스트에 저장한다.
4. 문자의 끝까지 모두 계산하고, 만약 마지막 문자의 최소에너지 값이 sys.max값이면 -1을 출력, 그렇지 않으면 저장된 값을 출력한다.
이해가 안되면 코드를 확인해보는걸 추천한다. 코드를 보면 더 이해가 쉬워서. 다른 사람들 풀이를 봣는데 비슷한 사람도 있고 아닌 사람도 있고. 전반적으로 논리는 다 똑같다. 당연하겠지만ㅋ
그냥 적당히 풀었는데 python3 풀이중에서는 3등을 기록했다. 이런적 처음인뎅ㅋㅋ 나이스!! 조금 수정해볼까 하고 했다가 오히려 성능이 안좋아져서; ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 그냥 처음 풀이가 제일 잘나왔다.