[Java] 백준 12026. BOJ 거리

정석·2024년 5월 27일

Java

알고리즘 학습

목록 보기

54/67

문제

💡문제 분석 요약

B O J 순서대로 보도 블럭을 밟을 수 있다.
각 보도블럭을 건너는 에너지는 보도블럭의 거리에 제곱이다.
주어진 보도블럭 조합으로 건널 수 있는 최소의 에너지를 구해라.

💡알고리즘 설계

최소 값을 구하는 목적이므로, 각 연산을 저장할 배열을 초기화 할 때 Integer.MAX_VALUE 로 int 최댓값 넣어 초기화 한다.
처음부터 시작하여 보도블럭을 밟을 때 B -> O 또는 O -> J 또느 J -> B 로 밟을 수 있으므로 이를 체크하는 메서드를 만든다.
보도블럭을 밟을 수 있다면 에너지를 계산하는데, 에너지는 거리의 차를 제곱한다.

💡코드

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


public class Main {
	
	public static void main (String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		
		String blocks = br.readLine();
		
		int[] dp = new int[N];
		Arrays.fill(dp, Integer.MAX_VALUE);
		dp[0] = 0;
		
		for (int i = 0; i < N; i++) {
			for (int j = i + 1; j < N; j++) {
				if (canJump(blocks.charAt(i), blocks.charAt(j)) && dp[i] != Integer.MAX_VALUE) {
					int energe = (j-i) * (j-i);
					dp[j] = Math.min(dp[j], dp[i] + energe);
				}
			}
		}
		
		if (dp[N-1] == Integer.MAX_VALUE) {
			System.out.println(-1);
		} else {
			System.out.println(dp[N-1]);
		}
	}
	
	private static boolean canJump(char from, char to) {
		if (from == 'B' && to == 'O') return true;
		if (from == 'O' && to == 'J') return true;
		if (from == 'J' && to == 'B') return true;
		
		return false;
		
	}
}