[DP] BOJ 거리 - 백준

https://www.acmicpc.net/problem/12026

12026번: BOJ 거리

 

참고 포스팅

https://hjp845.tistory.com/167

https://ngwoon.github.io/boj/2021/04/07/BOJ-%EA%B1%B0%EB%A6%AC/

 

B O J 순으로 가 최종 목적지에 도달할 때 드는 가장 최소의 비용을 계산하는 문제이다.

B - O - J 로 가는 경우의 수를 Greedy하게 푸는 것이 가장 최적이라고 생각했지만

다음 반례를 생각해보면 Greedy가 최적의 solution을 보장해주지 못한다.

 

다음 반례를 보자

15

BJBOJOJOOJOBOOO

 

 

다음의 경우 각 노드로 갈 수 있는 그 때 그 때의 solution은

BJBOJOJOOJOBOOO

빨간 색의 루트로 가는 경우가 해당하지만

첫 번째 O를 선택할 때 꼭 가장 가까운 O가 최적을 보장해준다고 볼 수 는 없다.

 

 

즉, 이는 경우의 수 문제로 생각해볼 수 있고

경우의 수는 보통

완전 탐색이나 DP로 접근을 하게 된다.

 

 

완전 탐색의 경우 N=1000이라도 시간이 굉장히 많이 들기 때문에 2초 안에 문제는 풀 수 없다고 판단하였고

DP 문제로 접근을 시도하였다.

 

 

첫 번째 시도하였던 방법은 완전 탐색의 방법을 메모이제이션을 사용하여 접근을 시도했지만

구현 부분에 있어 다소 복잡하였고 솔루션을 찾을 수 없었다.

 

 

그렇다면 DP의 다른 방법인 점화식을 찾는 방법이 존재하는데

점화식을 구상하기 어려워 주변의 풀이들을 참고해본 결과

문제를 풀 수 있었다.

 

 

dp[i]에는 i 문자에 올 때 최적의 비용을 계산해 놓는다

j는 i보다 이전의 경우를 의미한다고 할 때(j < i),

또, j에서 i로 넘어갈 수 있다고 할 때(즉, i가 O이면 j는 B이고, i가 J이면 j는 O이다)

다음 점화식을 만족한다.

 

min(dp[i], dp[j]+(i-j)2)

여기서 dp[i]의 min이 들어간 경우는 자체가 최적을 의미한다고 가정했기 때문이다

 

이 경우 파이썬 코드로는 다음과 같이 구현된다

 

구현 부에도 학습할 부분이 있으니 다음에 복습할 때도 꼭 참고하자

n = int(input())

route = input()

dp = [float('Inf')]*n
dp[0] = 0
for i in range(1,n) :
    for j in range(i) :
        if route[i] == 'B' :
            if route[j] == 'J' :
                dp[i] = min(dp[i], dp[j]+(i-j)**2)

        if route[i] == 'O' :
            if route[j] == 'B' :
                dp[i] = min(dp[i], dp[j]+(i-j)**2)

        if route[i] == 'J' :
            if route[j] == 'O' :
                dp[i] = min(dp[i], dp[j]+(i-j)**2)

print(dp[n-1] if dp[n-1] != float('Inf') else -1)

우선 코드를 하나씩 살펴보면

dp = [float('Inf')]*n을 한 이유는 우선 다 maximize한 다음에 하나씩 업데이트 해나가는 방식으로 아이디어를 생각했고

맨 첫 번째의 경우는 따로 비용이 발생하지 않으므로 0으로 초기화를 수행해주었다.

 

반복문 구성의 경우 i는 뒤의 것을 의미하므로 1~n까지 구성하였고

j는 i 이전 것을 지칭하므로 range(i)로 표현하였다

 

마지막으로 print구문을 보면

다음과 같이 3항 연산으로 표현하는 것에도 익숙해지자

굳이 또 for문을 돌려 불필요한 연산을 방지하는 것도 스킬이다

dp[n-1] if dp[n-1] != float('Inf') else -1