12026 BOJ 거리

 

어떻게 풀지 계속 고민하다가 앞자리 동기분의 도움을 받았다. 

 

문제 보자마자 뭔가 dp의 느낌이 들었고 값이 반복되는 부분이 있어서 이걸 저장해야 겠다고 생각했는데 식을 어떻게 세워야 할지 감이 안 잡혔다. b -> O -> J 순서로 반복되기도 하고.. 그러다 힌트 받고 다시 고민해보았다.

 

이걸 반복문 한 번에 해결하려 하지 말고 반복문 두 번 써서 i가 B일 때 j가 O인 애들을 전부 업데이트 하는 식으로 해보라길래 이렇게 생각하니 어떻게 풀 수 있을지 감이 잡혔다. 

 

그래서 풀이 방법

 

먼저 -1로 초기화를 한다. 위의 사진 보면 i가 1인 J는 0번째부터 이어지는 값이 아니기 때문에 계산하면 안되는데 이걸 어떻게 할지 고민하다가 기존에 -1인 값은 넘어가도록 코드를 짰다. 만약 값이 이미 차있다면 이전 숫자로부터 이어져있다고 간주하고.

 

다음으로 i를 기준으로 잡고 i의 다음 알파벳의 값을 계산해준다. i가 B였다면 i 이후에 있는 O값들의 거리를 전부 계산해준다. 이 과정을 반복하면 답을 구할 수 있다. 

 

와... 이렇게도 풀 수 있다니 신기했고 새로운 걸 알아간다. 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <bitset>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()

using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using iis = pair<int, string>;
using ii64 = pair<i64, i64>;
using iii = tuple<int, int, int>;

int dp[1005];

char find_nxt(char c)
{
    if (c == 'B')
        return 'O';
    if (c == 'O')
        return 'J';
    if (c == 'J')
        return 'B';
    return 'Z';
}

int     main()
{
    int n;
    string str;

    cin >> n >> str;
    
    memset(dp, -1, sizeof(dp));

    dp[0] = 0;
    for (int i = 0; i < n; i++)
    {
        if (dp[i] == -1)
            continue;

        char nxt = find_nxt(str[i]);
        for (int j = i + 1; j < n; j++)
        {
            if (nxt != str[j])
                continue;

            if (dp[j] == -1)
                dp[j] = dp[i] + (j - i) * (j - i);
            dp[j] = min(dp[i] + (j - i) * (j - i), dp[j]);
        }
    }

    cout << dp[n-1];

    return 0;
}