[Algorithm] Baekjoon 12026번 : BOJ 거리

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

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
#include <numeric>
 
using namespace std;
 
const int maxNum = 0x3f3f3f3f;
int n;
int dp[1001] = { 0 };
string s;
 
char checkNext(char c)
{
    if (c == 'B') return 'O';
    else if (c == 'O') return 'J';
    else return 'B';
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n;
    cin >> s;
 
    memset(dp, 0x3f, sizeof(dp));
 
    dp[0] = 0;
 
    for (int i = 0; i < n; ++i)
    {
        char cur = s[i];
        char next = checkNext(cur);
 
        for (int j = i+1; j < n; ++j)
        {
            if (s[j] == next)
            {
              dp[j] = min(dp[j], dp[i] + (int)pow(j - i, 2));
            }
        }
    }
 
    if (dp[n - 1] == maxNum) cout << -1;
    else cout << dp[n-1];
}
 
 
 

 

 

규칙에따라 블럭을 선택해서 N번쨰 블럭까지 도달해야할 때, 최소의 비용으로 도달해야하는 문제이다.

B O J 순서로 블럭을 선택해야하는데 3칸을 점프하려면 3*3 == 9의 비용을 소모한다.

그렇기 때문에 최대한 한칸씩 이동하는게 베스트지만, B O J 순서로 건너야 하기 때문에 어쩔수없이 바로 옆칸이 아니면 제곱의 비용을 소모해야 한다.

 

Bottom-Up방식으로 풀이했으며, 첫번째블럭부터 기준을 잡고 이후의 블럭들에 대해 dp테이블을 업데이트한다.

이동할 수 있는 블럭이라면 (B O J순서가 맞다면), 현재 블럭의 dp값 + 소모비용을 dp테이블에 최소값으로 업데이트한다.

 

바로 옆칸일 경우 +1인데, 제곱해도 1이기 때문에 해당점화식 하나만 있으면 된다.