백준 BOJ 12026 - BOJ 거리

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

12026번: BOJ 거리

이 역시 O(N^2) 문제다

디피 짤때 -1을 INF로 따로 처리한다는게 좀귀찮았다.

 

chtoin map은 글씨를 임의 인덱스로 변환시키고

intoch array는 인덱스를 글씨로 변화시킨다

(k+2)%3을 해준 이유는

(k-1)%3과 동일한 역할을 하면서

C언어에서 음수에 %연산할때 생기는 오류를 막기 위해서이다.

 

inf는 편의상 0x3f3f3f3f = 1061109567으로 했다.

사실 잘 안쓰는데 memset하려니 귀찮아서 이번엔 이걸로 해봤다.

 

dp 점화식은 주석으로 써뒀다.

 

#include <bits/stdc++.h>
using namespace std;

int dp[1234] = {0};

map<char,int> chtoin;
char intoch[3];


int main(){
	cin.sync_with_stdio(false);
	cin.tie(NULL);
	
	int N;
	string s;
	cin >> N;
	cin >> s;
	
	memset(dp, 0x3f, sizeof(dp));
	dp[0] = 0;
	
	chtoin['B'] = 0;
	chtoin['O'] = 1;
	chtoin['J'] = 2;
	
	intoch[0] = 'B';
	intoch[1] = 'O';
	intoch[2] = 'J';
	
	for(int i=1; i<N; i++){
		for(int j=0; j<i; j++){
			if(s[j] == intoch[(chtoin[s[i]]+2) % 3] && dp[j] != -1){
				dp[i] = min(dp[i], dp[j] + (i-j)*(i-j));
			}
		}
	}
	
	if(dp[N-1] == 1061109567) cout << -1;
	else cout << dp[N-1];
	return 0;
}
/*
dp[i] = i번째를 밟았을때 에너지 최솟값

dp[i] = 이전글씨일때의 j에 대하여 dp[j] + (i-j)^2; 
*/