[ 백준 12026 ] BOJ 거리 (C++)

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

12026번: BOJ 거리

 

정답률 보고 쉬울줄 알았는데 생각보다 잘 안 풀렸던 문제다. 우선 dp 문제이기 때문에 dp를 먼저 정의하자.

dp[i] : i까지 오는데 필요한 최소 에너지 양

 

알고리즘은 다음과 같이 짰다. 

모든 기준점에서 가능한 다음 문자를 찾고 에너지 양을 갱신해준다.

1)
모든 i에 대해,
input[i]는 input[i + 1] ~ input[n]까지 가능한 문자를 찾는다.
input[i] = 'B'라면 가능 문자는 'O'
input[i] = 'O'라면 가능 문자는 'J'
input[i] = 'J'라면 가능 문자는 'B'

2) 
가능 문자를 찾았으면 에너지 양을 갱신해준다.
가능 문자의 인덱스를 j라고 했을때,
만약 dp[j] = 0 이면 (j - i) * (j - i) 를 넣어준다.
만약 dp[j] !=0 이면 dp[j]와 dp[i] + (j - i) * (j - i) 중 최소값을 넣어준다.

 

1)에서 dp[i] 값이 0이면 가능한 경로가 아니기 때문에 건너뛴다. 그 이유는 위 알고리즘에서는 가능한 경로이면 항상 dp[i]에 0이 아닌 값이 들어가기 때문이다. 그런데 시작점은 항상 dp[i] = 0 이므로 시작점만 따로 2) 과정을 거치고 시작한다. 

 

마지막에 dp[n] = 0이면 n까지 가능한 경로가 없다는 뜻이므로 -1을 출력해주고, 값이 0이 아니면 dp[n]을 그대로 출력해주면 된다.

 

정답 코드는 아래와 같다.

 

#include <iostream>
#include <algorithm>
using namespace std;

char input[1001];
int dp[1001];
int n;

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> input[i];

	// 시작점에서 'O'만 먼저 찾아준다
	// 이레 반복문에서 시작점은 pass되기 때문.
	char now = 'B', find = 'O';
	for (int j = 2; j <= n; j++) {
		if (input[j] == find) 
			dp[j] = dp[1] + ((j - 1) * (j - 1));
	}


	for (int i = 1; i <= n; i++) {
		// dp[i]가 0이면 불가능한 경로이므로 pass
		if (dp[i] == 0) continue;

		now = input[i];
		if (now == 'B') find = 'O';
		if (now == 'O') find = 'J';
		if (now == 'J') find = 'B';

		for (int j = i + 1; j <= n; j++) {
			// 가능한 경로 탐색
			if (input[j] == find) {
				if (dp[j] == 0) // 처음 방문이면 가준다
					dp[j] = dp[i] + ((j - i) * (j - i));
				else // 재방문이면 최소값 저장
					dp[j] = min(dp[j], dp[i] + ((j - i) * (j - i)));
			}
		}
	}

	if (dp[n] == 0)
		cout << -1 << endl;
	else
		cout << dp[n] << endl;

	return 0;
}