[백준 1463번 / Java] 1로 만들기 - DP

문제 링크

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

1463번: 1로 만들기

---

 

 

 

 

풀이

자기 전에 문제 하나 풀고 자야지~~ 하면서 풀었던 문제

실버 3 문제라 DP로의 접근은 쉬웠으나, 뜻하지 않게 ArrayIndexOutOfBounds Exception으로 고생했음..

반 졸린 상태에서 풀어서~~ 라고 핑계를 대보지만.

실수를 줄이기 위해 항상 신경써야겠다고 다짐한 문제로. 상기시키기 위해 포스팅....

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

public class BaekJoon1463 {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int X = Integer.parseInt(br.readLine());

        int[] dp = new int[X+1];

        dp[1] = 0;

        for(int i = 2; i <= X; i++){
            dp[i] = dp[i-1] + 1;
            if(i % 6 == 0) dp[i] = Math.min(dp[i/3] + 1, Math.min(dp[i/2] + 1, dp[i]));
            else if(i % 3 == 0) dp[i] = Math.min(dp[i], dp[i/3] + 1);
            else if(i % 2 == 0) dp[i] = Math.min(dp[i], dp[i/2] + 1);
        }

        System.out.println(dp[X]);
    }
}

 

계속 오답을 제출했던 이유는, 처음 dp배열 초기화에 있었는데,

2일 때도 1이고, 3일 때도 1이기 때문에, dp[2]와 dp[3]의 값 모두 1로 설정해놓아서 X가 1일 때, 2일 때 예외상황이 발생했음;;;;;;;;;

 

졸릴 땐 자는걸로 하고.. 좋은 컨디션으로 문제를 풀어나가야겠다..