[백준] 12026번 : BOJ 거리 Silver1(실버1) - JAVA[자바]

[Silver I] BOJ 거리 - 12026

문제 링크

성능 요약

메모리: 16036 KB, 시간: 172 ms

분류

다이나믹 프로그래밍

제출 일자

2023년 10월 26일 13:30:32

문제 설명

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

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

class Main
{
	public static void main(String args[]) throws Exception
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        String line = br.readLine();
        int[] arr = new int[line.length()];

        for(int i = 0; i < arr.length; i++){
            arr[i] = Integer.MAX_VALUE;
        }
        arr[0] = 0;
        
        char next;
        for(int i = 0; i < line.length(); i++){
            char cur = line.charAt(i);
            if(arr[i] == Integer.MAX_VALUE){
                continue;
            }
            if(cur == 'B'){
                next = 'O';
            }else if(cur =='O'){
                next = 'J';
            }else{
                next = 'B';
            }
            for(int j = i + 1; j < line.length(); j++){
                if(line.charAt(j) == next){
                    int nextValue = arr[i] + (j - i) * (j - i);
                    arr[j] = Math.min(arr[j],nextValue);
                }
            }
        }
        
        bw.write((arr[n-1] == Integer.MAX_VALUE ? -1 : arr[n-1]) +"\n");
        bw.flush();
        bw.close();
    }
    
}