[백준 12026번] BOJ 거리 (C++)

문제링크 : https://www.acmicpc.net/problem/12026

12026번: BOJ 거리

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N;
char arr[1001];
int dp[1001];

bool check(char cur, char next) //BOJ 순서 확인
{
    if(cur=='B' && next == 'O') return 1;
    if(cur=='O' && next == 'J') return 1;
    if(cur=='J' && next == 'B') return 1;
    return 0;
}

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    cin >> N;
    for(int i=1; i<=N; i++) 
    {
        cin >> arr[i];
        dp[i]=MAX; //초기화
    }
   
    dp[1] = 0;

    for(int i=1; i<=N; i++)
    {
        for(int j=i+1; j<=N; j++)
        {
            if(!check(arr[i], arr[j])) continue;
            dp[j] = min(dp[j], (j-i)*(j-i) + dp[i]); //기존 + 새롭게 점프한 값
        }
    }

    cout << (dp[N] == MAX ? -1 : dp[N]); //불가능하면 -1 출력
    return 0;
}

 

BOJ의 순서를 확인한 이후에 dp를 갱신해주어야한다.

BOJ가 BO, OJ, JB 등 올바르게 순서가 되어있는지 우선 체크하고, 만약 순서가 올바르지 않다면 dp는 갱신하지 않는다.

이를 위해 check 함수를 따로 작성하였다.

 

이후 dp는 기존에 저장했던 (직전 값 dp[i]) 값과 새롭게 점프한 값인 (j-i)*(j-i)를 더해주어 현재 값인 dp[j]을 최소값으로 갱신해준다.

 

마지막에 무사히 도착점에 도달하기 불가능한 경우에 대해서 예외처리 (-1 출력) 을 해주는 것을 잊으면 안된다.