[백준] 12026번: BOJ 거리 (Java)

💡문제 분석 요약

1부터 N까지 보도블럭이 있고 B, O, J 순서로 이동할 수 있다. i번에서 I+1 ~ N번까지 이동할 수 있으며 k칸 이동하는데 k*k 에너지가 필요하다. 1부터 N까지 이동하는데 필요한 최소한의 에너지를 구하는 문제이다.

• 시간 제한: 2초
• 메모리 제한: 512MB

 

💡알고리즘 설계

모든 경로를 탐색하며 최소 경로 찾는 문제 ⇒ DP(동적계획법)의 Bottom-Up 방식

• `dp` 배열을 큰 값으로 초기화한다. (MAX로 초기화)
  `dp[0]`은 0으로 설정한다.
• 현재 위치 i에 대해, 이전의 모든 위치 j(0~i-1)를 검사한다. (현재: B→ 이전: J, O→B, J→ O)
  • ex) `street[i] == 'B' && street[j] == 'J'`
    : 현재 위치(i)가 'B'이고 이전 위치(j)가 'J'인 경우 (J → B 이동)
  • B→O→J 순서로 이동 가능하면, 에너지를 계산하고 최소값을 갱신한다. (`dp[i]`)
• `dp[N-1]` 을 결과값으로 반환한다.
  만약 초기값과 같으면 -1을 반환한다.

 

💡코드

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

public class Main {
    static int N;
    static char[] street;
    static int MAX = 10000001;

    static void findMinEnergy() {
        int[] dp = new int[N];
        Arrays.fill(dp, MAX);
        dp[0] = 0;

        for(int i=1; i<N; i++) { // 현재 위치
            for(int j=0; j<i; j++) { // 이전 위치
                if(street[i]=='B' && street[j]=='J'
                || street[i]=='O' && street[j]=='B'
                || street[i]=='J' && street[j]=='O') {
                    int energy = (i-j)*(i-j);
                    dp[i] = Math.min(dp[i], dp[j]+energy);
                }
            }
        }

        int result = dp[N-1] == MAX ? -1 : dp[N-1];
        System.out.println(result);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        street = br.readLine().toCharArray();
        findMinEnergy();
    }
}

 

💡시간복잡도

$O(N^2)$

 

💡 느낀점 or 기억할정보

모든 경로를 탐색하는 방법이어서 바로 Bottom-Up 방식을 사용하기로 결정했지만, 막상 B→O→J 순서로 이동 가능한지 확인하고 최솟값을 계산해서 배열을 저장하는 방법을 생각하는 것은 오래걸렸다ㅠ