[BOJ] 12026번: BOJ거리

문제 내용

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

12026번: BOJ 거리

 

풀이 시간

10분

 

풀이 과정

문제를 읽어보는 중에 그리디 혹은 DP라고 생각했고, 다 읽어보니 DP라는 확신이 들었음.

이후 상향식과 하향식중 어느쪽으로 할까 고민했고, 구현하기 편한 상향식으로 풀이를 결정함.

 

BOJ순으로 발판을 밟아야 한다.

index 0부터 현재 발판에 다음 발판을 찾아가는건 시간적으로 낭비라고 생각함.

따라서 먼저 전체발판을 1회 순회하면서 B,O,J에 해당하는 index를 따로 모아둠.

 

이후 dp값을 찾는 상향식 과정에서 현재 발판을 기준으로 다음에 밟아야하는 발판의 해당하는 index만 확인해서 시간을 줄임.

 

정답 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	static int N,INF=1_000_001; //최대값 :100만, 최대값 이상으로 설정
	static List<Integer>[] boj=new List[3]; //각 발판별 index를 담을곳
	static int[] dp;
	public static void main(String[] args) throws Exception{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		N=Integer.parseInt(br.readLine());
		char[] board=br.readLine().toCharArray();
		dp=new int[N];
		
		Arrays.fill(dp, INF);
		
		for(int i=0;i<3;i++) {
			boj[i]=new ArrayList<>();
		}
		
        //1회 순회 : 발판 분류 
		for(int i=0;i<N;i++) {
			if(board[i]=='B') {
				boj[0].add(i);
			}
			else if(board[i]=='O') {
				boj[1].add(i);
			}
			else{
				boj[2].add(i);
			}
		}
		
        //2회 순회 : DP(최소값 찾기)
		dp[0]=0;
		for(int i=0;i<N-1;i++) {
			if(board[i]=='B') {
				input(1,i);
			}
			else if(board[i]=='O') {
				input(2,i);
			}
			else{
				input(0,i);
			}
		}
		
        //끝점에 방문 했는지 체크
		int result=(dp[N-1]==INF)?-1:dp[N-1];
		System.out.println(result);
	}
	
	static void input(int bojIdx,int idx) {
		for(int nextIdx:boj[bojIdx]) {
			if(nextIdx<idx) continue;
			int power=(int)Math.pow(nextIdx-idx, 2);
			
			dp[nextIdx]=Math.min(dp[nextIdx], dp[idx]+power);
		}
	}
}