[Silver I] BOJ 거리 - 12026

문제 링크

성능 요약

메모리: 15000 KB, 시간: 116 ms

분류

다이나믹 프로그래밍

제출 일자

2024년 8월 28일 19:55:07

문제 설명

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을 출력한다.

풀이 (DP)

처음엔 Stack에 마지막 문자를 저장하는 방식으로, Stack의 FILO 구조를 이용한 풀이를 짰었는데... 예제 6번에서 막혀서 코드를 다시 짰다...

---

예제 6번
입력

15
BJBOJOJOOJOBOOO

출력

52

---

내가 Stack으로 짤 때 실수했던 부분은 문자상의 거리를 기준으로 최대한 짧은 문자를 Stack에 저장해가며 B -> O -> J 순서를 고집했다.
그래서 예제 6번에서 마지막 BOOO를 처리할 때 B와 만나는 가장 첫번째 O를 처리하고 마지막 n까지 도달하지 못해 -1를 출력시켰었다.

이런 부분을 인지하고 최대한 예제 6번을 의식하면서 코드를 짰다. 바로 다음 문자를 만나면 최소인지 비교하는 방식을 사용해 dp 배열을 초기화해가는 방식을 사용해 해결할 수 있었다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;


public class Main {
	//dp 문제
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		
		char[] BOJ = new char[n]; //BOJ 문자 배열
		BOJ = br.readLine().toCharArray();
		
		long[] dp = new long[n];
		Arrays.fill(dp, Integer.MAX_VALUE);
		
		dp[0]=0;
		
		for(int i=0; i<n-1; i++) { // B -> 0 -> J 순으로 탐색
			char word = BOJ[i];
			if(word=='B') {
				for(int j=i+1; j<n; j++) {
					char next_word = BOJ[j];
					if(next_word=='O') {
						dp[j] = (long) Math.min(dp[j], (dp[i]+ Math.pow(i-j, 2)));
					}
				}
			}
			else if(word=='O') {
				for(int j=i+1; j<n; j++) {
					char next_word = BOJ[j];
					if(next_word=='J') {
						dp[j] = (long) Math.min(dp[j], (dp[i]+ Math.pow(i-j, 2)));
					}
				}
			}
			else {
				for(int j=i+1; j<n; j++) {
					char next_word = BOJ[j];
					if(next_word=='B') {
						dp[j] = (long) Math.min(dp[j], (dp[i]+ Math.pow(i-j, 2)));
					}
				}
			}
		}
		
		if(dp[n-1]==Integer.MAX_VALUE) {
			System.out.println(-1);
		}
		else {
			System.out.println(dp[n-1]);
		}
	}
}