[BOJ] BOJ거리(12026)

www.acmicpc.net/problem/12026

12026번: BOJ 거리

난이도 - 실버1

분류 - DP

 

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, ... 순서로 보도블록을 밟으면서 점프를 할 것이다.

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

입력

첫째 줄에 1 ≤ N ≤ 1,000이 주어진다.

둘째 줄에는 보도블록에 쓰여 있는 글자가 1번부터 순서대로 주어진다.

출력

스타트가 링크를 만나는데 필요한 에너지 양의 최솟값을 출력한다. 만약, 스타트가 링크를 만날 수 없는 경우에는 -1을 출력한다.

예제 입력 1 복사

9 BOJBOJBOJ

예제 출력 1 복사

8

예제 입력 2 복사

9 BOJBOJBOJ

예제 출력 2 복사

8

예제 입력 3 복사

8 BJJOOOBB

예제 출력 3 복사

-1

예제 입력 4 복사

13 BJBBJOOOJJJJB

예제 출력 4 복사

50

예제 입력 5 복사

2 BO

예제 출력 5 복사

1

예제 입력 6 복사

15 BJBOJOJOOJOBOOO

예제 출력 6 복사

52

풀이

 생각보다 간단하게 풀렸다. 아무래도 DP인데 2중 반복문을 쓰면 안될거라는 강박에 사로 잡혀 있는 것 같다. 차후에 코딩테스트에 대한 시간복잡도를 더 자세히 알아봐야 될것 같다.

 

1. 먼저 입력을 받은 후 arr을 모두 MX(N이 최대 1000이니 1000*1000이 최대거리이다 여기에 1을 더해 줬다.)로 초기화 해준다. (입력은 개인적으로 편하게 B=0, O=1, J=2로 받아서 (boj[i]+1)%3 과 다음에 오는 것이 같으면 올바른 순서라고 생각하며 코드를 짰다.)

2. arr[i]~arr[N]까지 돌아가며 (N-1까지여도 괜찮다.) arr을 채울 것인데 arr[i]가 MX인 경우는 (만약 boj[i]가 J일 경우 전에 O가 없었던 경우, B일때 J가 없었던 경우로 불가능 한 경우이다.) continue를 해준다.

3.  내부 포문으로 와서 j는 i 다음번부터 N까지중에 boj[j]가 boj[i]의 다음 것이 맞는지 확인 하면서 현재 자신의 값과 i~j의 차이값의 제곱+arr[i]의 값 중 작은 값을 저장한다.

4. 자연적으로 순서상 불가능한 것은 MX값이 들어가 있어 마지막에  arr[N]이 MX일 경우 -1을 출력한다.

코드

#include <iostream>
#include <vector>
#define MX 1000001
using namespace std;
int N;
vector<int> arr;
vector<int> boj;
int main() {
	cin.tie(0); cout.tie(0);
	ios_base::sync_with_stdio(0);
	cin >> N;
	arr.resize(N + 1, MX);
	boj.resize(N + 1, 0);
	string temp;
	cin >> temp;
	for (int i = 0; temp[i]; i++) {
		if (temp[i] == 'B')
			boj[i+1] = 0;
		else if (temp[i] == 'O')
			boj[i+1] = 1;
		else
			boj[i+1] = 2;
	}
    ///  여기까지 입력
    
    
	arr[1] = 0;
	for (int i = 1; i <= N; i++) {
		if (arr[i] == MX) continue;
		for (int j = i + 1; j <= N; j++) {
			if (boj[j] == (boj[i] + 1) % 3) { // 다음것이 맞음
				arr[j] = min(arr[j],(j - i) * (j - i)+arr[i]);
			}
		}
	}
	cout << (arr[N]!=MX?arr[N]:(-1));
	return 0;
}