[백준 1463] 1로 만들기 (JAVA)

백준 1463번 문제 - 1로 만들기

1463번: 1로 만들기

---

문제 분석

 

 

• 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력해라.
• 정수 N에 사용할 수 있는 연산은 다음과 같이 세가지 이다.
  • N가 3으로 나누어 떨어지면, 3으로 나눈다.
  • N가 2로 나누어 떨어지면, 2로 나눈다.
  • 1을 뺀다.
• 입력 받는 N은 1보다 크거나 같고, 10^6보다 작거나 같다.

---

 

해결 키 포인트

 

• DP로 구현
  • DP가 아니면 시간초과 발생 → 시간 제한 0.15초
• 10^6(1000000)까지 for문 반복시 걸리는 시간  → 약 0.01초
• 1부터 10^6까지 1을 만드는데 걸리는 시간 DP로 풀기
  • 쉽게 알 수 있는 dp 값 : dp[1] = 0 | dp[2] = 1 | dp[3] = 1
  • 위에 값들을 설정하고 4부터 10^6까지 반복
  • dp[i] 구하는법
    1. dp[i] = dp[i-1]로 초기화
    2. i가 3로 나누어떨어질 경우 : i % 3 == 0  
       - dp[i]와 dp[i/3] 중에 작은 값을 dp[i] 값으로 설정
    3. i가 2로 나누어떨어질 경우 : i % 2 == 0  
       - dp[i]와 dp[i/2] 중에 작은 값을 dp[i] 값으로 설정
    4. dp[i] 값 1 증가

---

코드

 

import java.io.*;

public class Main {
    public static int [] dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

        int N = Integer.parseInt(br.readLine());
        bw.write(dp[N] + "\n");

        bw.flush();
        bw.close();
    }
}