[Java] 12026 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을 출력한다.

문제 풀이

DP문제이다.

처음에는 그냥 idx 한 칸 씩  진행하면서 다음 단어인지 확인하면서 넘어가면 될거 같았는데 문제가 많았다.

시간도 2초로 적당하고 n의 수도 1000정도로 낮아서 이중 FOR문으로 하나씩 검사하면서 해당 칸에 도달하는 가장 작은 에너지 값을 저장해가면 충분히 가능할 것 같았다.

 

해당 칸에 도달하기 위한 최소 에너지를 기록하기 위한 dp 배열을 하나 만들고 Integer.MAX_VALUE로 채운다.

i = 1 칸부터 시작하여 해당 i칸에 도달하기 위한 가장 적은 에너지를 계산한다. j = 0부터 i전까지의 칸에서 i칸 전 단어가 기록된 칸을 기준으로 현 i칸의 에너지와 j칸 + i-j의 2제곱 한 값 중 작은 값을 계속 i칸에 갱신해가면서 계산한다.

 

이후 가장 마지막칸의 에너지 값을 출력한다.

자바 코드

import java.util.*;
import java.io.*;
import java.math.*;

public class BOJ {
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		char[] arr = br.readLine().toCharArray();
		int[] dp = new int[N];
		Arrays.fill(dp, Integer.MAX_VALUE);
		dp[0] = 0;
		for (int i = 1; i < dp.length; i++) {
			for (int j = 0; j < i; j++) {
				if(arr[i] == 'O' && arr[j] == 'B' && dp[j] != Integer.MAX_VALUE) {
					dp[i] = Math.min(dp[i], dp[j] + (i-j)*(i-j));
				}
				else if(arr[i] == 'J' && arr[j] == 'O' && dp[j] != Integer.MAX_VALUE) {
					dp[i] = Math.min(dp[i], dp[j] + (i-j)*(i-j));
				}
				else if(arr[i] == 'B' && arr[j] == 'J' && dp[j] != Integer.MAX_VALUE) {
					dp[i] = Math.min(dp[i], dp[j] + (i-j)*(i-j));
				}
				
			}
		}
		System.out.println((dp[N-1]==Integer.MAX_VALUE)?-1:dp[N-1]);
	}

}

 

이전 실패 코드

시간 초과

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;

public class BOJ {
    private static int N;
    private static String[] block;
    private static int result = Integer.MAX_VALUE;
    private static final String[] pointer = {"B", "O", "J"};
    private static int idx = 1;
    private static boolean flag = false;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        block = br.readLine().split("");

        go(0, 0);

        if(flag)
            System.out.println(result);
        else
            System.out.println(-1);
    }

    private static void go(int depth, int energy){
        if(depth == N - 1){
            flag = true;
            result = Math.min(result, energy);
            return;
        }

        if(energy > result)
            return;

        if(result < N){
            System.out.println(result);
            System.exit(1);
        }

        for(int i = depth + 1; i < N; i++){
            if(!pointer[idx].equals(block[i])) {
                continue;
            }

                idx = (idx + 1) % 3;
                go(i, energy + (int) Math.pow(i - depth, 2));
                idx = (idx + 2) % 3;
        }
    }
}