백준 (BOJ) 12026 BOJ 거리 java dp

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

12026번: BOJ 거리

 

이 문제 어딘가 https://verycrazy.tistory.com/122?category=1052323랑 닮아 있는데 좀 다른 문제.

백준 (BOJ) 21317 징검다리 건너기 java dp

 

정형적인 LIS와 비슷하게 풀 수 있는데, 약간 더 응용됐다고 보면 된다.

 

범위에 아슬아슬하게 맞춰 초기화해 풀었는데, -1로 dp 초기화해서 푸는 게 더 정직(?)하고 문제 없다고 할 수 있다.

 

문제를 어느정도 숙지하고 풀기 시작한 시점부터 왜 초기화가 문제인지 감을 잡게 되는 것 같다.

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int lth = Integer.parseInt(br.readLine());
        String str = br.readLine();

        int[] dp = new int[lth];
        for(int i=1; i<lth; ++i) dp[i] = 1000001; // -1 사용해서 진행하는 풀이도 있다.

        for(int i=1; i<lth; ++i){ // i=0은 무조건 B
            char prevShouldBe;
            if(str.charAt(i) == 'B'){
                prevShouldBe = 'J';
            }else if(str.charAt(i) == 'O'){
                prevShouldBe = 'B';
            }else{ // == 'J'
                prevShouldBe = 'O';
            }

            for(int j=0; j<i; ++j){
                if(str.charAt(j) == prevShouldBe){ // -1로 초기화했을 때 여기서 -1 체크해줘야 함
                    int diff = i - j;
                    int energy = diff * diff + dp[j]; // 이전 j 위치까지 도달하는데 사용한 에너지

                    dp[i] = Math.min(energy, dp[i]);
                }
            }
        }



        if(dp[lth-1] == 1000001){
            System.out.print(-1);
        }
        else{
            System.out.print(dp[lth-1]);
        }

    }
}