BOJ 12026

BOJ거리

문제출처

문제 해석

  • 스타트(1번)가 링크의 집(N번)으로 점프해서 갈 수 있는 최소 에너지의 양을 구하는 문제입니다.
  • 주어진 배열에서 ‘B’->’O’->’J’ 순서로 점프할 수 있으며, 점프할 때의 에너지 양은 (점프하는 위치 - 현재위치)2입니다.
  • 링크의 집에 도착하는데 필요한 최소의 에너지 양을 구하되 집에 도착할 수 없으면 -1을 출력합니다.

설계(10)

  • 전형적인 1차원 dp문제로 D[i] = i번째까지 점프할 때 드는 최소의 에너지 양으로 점화식을 세울 수 있습니다.
  • pos+1 ~ N 까지 가능한 모든 곳을 탐색해야 하므로, O(N^2)의 시간복잡도가 걸리게 됩니다.
  • B O J 순서로 뛰기 위하여 각 B O J 를 0,1,2로 변환한 후 현재위치의 숫자 + 1 == 다음 위치의 숫자 인 경우에만 탐색하도록 하였습니다.

구현(10)

코드
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
#define MAXN 1000
#define INF 987654321
int cache[MAXN];
int map[MAXN];
int N;
int dp(int pos) {
	if (pos == N - 1) return 0;
	int& ret = cache[pos];
	if (ret != -1) return ret;
	ret = INF;
	for (int i = pos + 1; i < N; i++) {
		if ((map[pos] + 1) % 3 == map[i]) {
			ret = min(ret, dp(i) + (i - pos) * (i - pos));
		}
	}
	return ret;
}
int main() {
	scanf("%d", &N);
	memset(cache, -1, sizeof(cache));
	for (int i = 0; i < N; i++) {
		char tmp;
		scanf(" %1c", &tmp);
		if (tmp == 'B') map[i] = 0;
		else if (tmp == 'O') map[i] = 1;
		else map[i] = 2;
	}
	int ans = dp(0);
	ans = (ans == INF) ? -1 : ans;

	printf("%d", ans);
	return 0;
}
디버깅
제출결과
  • 0ms

    마무리