[JAVA] 백준 1463: 1로 만들기

문제

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

---

[Do it! 알고리즘 코딩테스트 자바편]

과정

1. 문제 분석 & 풀어보기

dp[i]: i에서 1로 만드는 데 걸리는 최소 연산 횟수

dp[i] = dp[i - 1] + 1
if(i % 2 == 0) dp[i] = min(dp[i], dp[i / 2] + 1)
if(i % 3 == 0) dp[i] = min(dp[i], dp[i / 3] + 1)

3. 코드

package Baekjoon;

import java.io.IOException;
import java.util.Scanner;

public class S3_1463 {

  public static void main(String[] args) throws IOException {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int[] dp = new int[n + 1];
    //dp[x] = x에서 1로 만드는 최소 횟수

    dp[1] = 0;

    for (int i = 2; i <= n; i++) {
      dp[i] = dp[i - 1] + 1;
      if(i % 2 == 0) dp[i] = Math.min(dp[i], dp[i / 2] + 1);
      if(i % 3 == 0) dp[i] = Math.min(dp[i], dp[i / 3] + 1);
    }
    
    System.out.println(dp[n]);
    
  }//main
}//class

---

package Baekjoon;

import java.io.IOException;
import java.util.Scanner;

public class S3_1463 {

  public static void main(String[] args) throws IOException {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int[] dp = new int[n + 1];
    //dp[x] = x에서 1로 만드는 최소 횟수

    dp[2] = 1;
    dp[3] = 1;

    for (int i = 4; i <= n; i++) {
      dp[i] = dp[i - 1] + 1;
      if(i % 2 == 0) dp[i] = Math.min(dp[i], dp[i / 2] + 1);
      if(i % 3 == 0) dp[i] = Math.min(dp[i], dp[i / 3] + 1);
    }
    
    System.out.println(dp[n]);
    
  }//main
}//class

처음에는 이렇게 짰는데, n이 4 이하면 94%에서 index Error가 나서 실패한다!