[C/C++] 백준 - 12026번 : BOJ 거리

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

12026번: BOJ 거리

문제

BOJ 거리는 보도블록 N개가 일렬로 놓여진 형태의 도로이다. 도로의 보도블록은 1번부터 N번까지 번호가 매겨져 있다.

스타트의 집은 1번에 있고, 링크의 집은 N번에 있다. 스타트는 링크를 만나기 위해서 점프해가려고 한다.

BOJ거리의 각 보도블록에는 B, O, J 중에 하나가 쓰여 있다. 1번은 반드시 B이다.

스타트는 점프를 통해서 다른 보도블록으로 이동할 수 있다. 이때, 항상 번호가 증가하는 방향으로 점프를 해야 한다. 만약, 스타트가 현재 있는 곳이 i번이라면, i+1번부터 N번까지로 점프를 할 수 있다. 한 번 k칸 만큼 점프를 하는데 필요한 에너지의 양은 k*k이다.

스타트는 BOJ를 외치면서 링크를 만나러 가려고 한다. 따라서, 스타트는 B, O, J, B, O, J, B, O, J, ... 순서로 보도블록을 밟으면서 점프를 할 것이다.

스타트가 링크를 만나는데 필요한 에너지 양의 최솟값을 구하는 프로그램을 작성하시오.

 

 

B-O-J의 순서를 지키면서 모든 경우의 수를 확인해보고 이미 같은 방법으로 방문했었던 지역은 메모이제이션으로 값만 돌려받으면 시간 내 해결이 가능한 동적계획법 문제이다.

#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <set>
#include <map> 
#define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ENDL cout << endl
#define ll long long	
#define ull unsigned long long
#define INF 987654321
#define Mod 1000000
#define endl '\n'
#define pil pair<int,int>

using namespace std;

int N;
string board;
int cache[1003][1003];

void input() {
	cin >> N;
	cin >> board;
}

int path(int index, int jump) {
	if (index >= N-1) return 0;
	int& ret = cache[index][jump];
	if (ret != -1) return ret;
	ret = INF;
	for (int next = index + 1; next < N; ++next) {
		int power = next - index;
		if (board[index] == 'B' && board[next]=='O') {
			ret = min(ret, path(next, power) + power * power);
		}
		if (board[index] == 'O' && board[next] == 'J') {
			ret = min(ret, path(next, power) + power * power);
		}
		if (board[index] == 'J' && board[next] == 'B') {
			ret = min(ret, path(next, power) + power * power);
		}
	}
	return ret;
}

int solution() {
	memset(cache, -1, sizeof(cache));
	int answer = path(0, 0);
	return answer == INF ? -1 : answer;
}

int main() {
	fastio;
	input();
	cout << solution() << endl;

	return 0;
}