백준 12026 BOJ 거리, c++

 

 

 

처음 작성한 코드는 다음과 같다.

하지만 틀렸다는 결과가 나왔다.

#include <iostream>
using namespace std;

int main(){
    int n;
    cin >> n;
    
    char arr[n];
    for(int i=1; i<=n; i++)
        cin >> arr[i];
    
    char now = 'B';
    int now_num = 1;
    int result = 0;
    for(int i=2; i<=n; i++){
        if (now=='B' && arr[i]=='O'){
            result += ((i-now_num)*(i-now_num));
            now = 'O';
            now_num = i;
            continue;
        } 
        else if (now=='O' && arr[i]=='J') {
            result += ((i-now_num)*(i-now_num));
            now = 'J';
            now_num = i;
            continue;
        }
        else if (now=='J' && arr[i]=='B') {
            result += ((i-now_num)*(i-now_num));
            now = 'B';
            now_num = i;
            continue;
        }
        
        if(i==n)
            result = -1;
    }
    
    cout << result;
    
    return 0;
}

 

 

 

위 코드로 실험해봤을 때, 간단한 예제는 통과했으나 복잡한 예제는 실패했다.

문제가 됐던 부분은,

이 문제의 목표는 마지막 n번째 배열에 도착하는 것이기 때문에

전까지는 최소단위로 점프하다가 마지막에는 앞에 가능한 문자가 있어도 n번째 배열로 점프해줘야한다는 것이다.

ex. BOOO => 최소단위로 점프해야하지만, 동시에 n번째 배열로 도착해야하기 때문에 그 전에 가능한 'O'가 있어도 마지막 배열의 'O'로 가줘야 한다.

ex. 또 "BJBOJOJOOJOBOOO" 인 경우에는 중간에 어떤 O와 J를 선택하냐에 따라 값이 달라진다.

따라서 마냥 최소의 경우(마냥 가장 가까운 문자로 점프하면 안됨)로 고려해주면 안된다.

 

 

 

수정한 코드는 다음과 같다.

이렇게 최소의 경우를 구하는 게 아니라 전체를 고려하고 그 중 최소를 구해야 할때 다이나믹 프로그래밍 (DP)를 사용하면 된다.

다이나믹 프로그래밍을 사용해서, 2부터 n까지 각 지점에 도달하려면 걸리는 최소 경우를 계산해 주는 것이다. 

그럼 최소끼리 더해서 마지막의 dp[n]의 값은 최소가 된다.