[Java] baekjoon_1463 : 1로 만들기

다이나믹 프로그래밍

1로 만들기 : Silver3

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

1463번: 1로 만들기

 

 

 

 

풀이

import java.io.*;

public class Main {
  private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
  
  public static void main(String[] args) throws IOException {
    int N = Integer.parseInt(br.readLine());
    br.close();
    
    int[] dp = new int[N + 1];
    dp[1] = 0; // 1은 이미 1이므로 연산 횟수가 0이다.

    // 연산 횟수 갱신
    for (int i = 2; i <= N; i++) {
      dp[i] = dp[i - 1] + 1; // 1을 빼는 경우
      if (i % 2 == 0)
        dp[i] = Math.min(dp[i], dp[i / 2] + 1); // 2로 나누는 경우
      if (i % 3 == 0)
        dp[i] = Math.min(dp[i], dp[i / 3] + 1); // 3으로 나누는 경우
    }
    bw.write(dp[N] + "\n");
    bw.close();
  }
}

 

ㄴ 먼저, 주어진 수 N을 1로 만드는 최소 연산 횟수를 저장할 배열을 생성했다.

ㄴ Bottom-up 방식으로 다이나믹 프로그래밍을 수행하도록 했다.

 

ㄴ 각 인덱스 i에 대해 아래와 같이 최소 연산 횟수를 갱신한다.
현재 수 i에서 1을 빼는 경우 => dp[i] = dp[i - 1] + 1
현재 수 i를 2로 나누는 경우 => dp[i] = dp[i / 2] + 1
현재 수 i를 3으로 나누는 경우 => dp[i] = dp[i / 3] + 1

 

=> 주어진 수 N에 대한 최소 연산 횟수인 dp[N]을 반환하도록 한다.

 

• 1을 빼는 경우 (dp[i-1] + 1)
  ㄴ 현재 수에서 1을 빼는 경우를 고려하여 연산 횟수를 구한다.
  ㄴ 이전 단계에서 1을 빼는 연산을 통해 얻은 결과에 1을 더하면 현재 수에 대한 최소 연산 횟수가 된다.
• 2로 나누는 경우 (dp[i/2] + 1)
  ㄴ 현재 수가 2로 나누어 떨어지는 경우를 고려하여 연산 횟수를 구한다.
  ㄴ 현재 수를 2로 나눈 수에 대한 최소 연산 횟수에 1을 더하면 현재 수에 대한 최소 연산 횟수가 된다.
• 3으로 나누는 경우 (dp[i/3] + 1)
  ㄴ 현재 수가 3으로 나누어 떨어지는 경우를 고려하여 연산 횟수를 구한다.
  ㄴ 현재 수를 3으로 나눈 수에 대한 최소 연산 횟수에 1을 더하면 현재 수에 대한 최소 연산 횟수가 된다.

 

 

Bottom-Up 방식

1로 만들어야 할 수 N을 입력받은 뒤, 
2~N까지 수들에 대한 최적의 해(최소 연산 횟수)를 DP 테이블에 차례로 저장한다.

 

1. 예를 들어 N이 2일 경우, 2를 1로 만드는데 필요한 최소 연산 횟수는 아래 두 가지 경우의 연산 횟수 중 최소값이다.

ㄴ f(2)의 값을 구하기 위해서는 f(1)의 값이 필요하다.
첫 번째 연산이 -1일 경우 => 1로 만들기 위한 최소 연산 횟수(dp[1]) + -1연산 한번 = 0 + 1 = 1
첫 번째 연산이 /2일 경우 => 1로 만들기 위한 최소 연산 횟수(dp[1]) + /2연산 한번 = 0 + 1 = 1

=> 두 가지 값을 비교해본 결과 2을 1로 만들기 위한 최소 연산횟수는 1임을 알 수 있다.

2. 예를 들어 N이 6일 경우, 6을 1로 만드는데 필요한 최소 연산 횟수는 아래 세 가지 경우에서 연산 횟수 중 최소값을 구해야 한다.

첫 번째 연산이 -1일 경우 => 1로 만들기 위한 최소 연산 횟수(= dp[5]) + 1 = 3 + 1 = 4
첫 번째 연산이 /2일 경우 => 1로 만들기 위한 최소 연산 횟수(= dp[3]) + 1 = 1 + 1 = 2
첫 번째 연산이 /3일 경우 => 1로 만들기 위한 최소 연산 횟수(= dp[2]) + 1 = 1 + 1 = 2

=> 세 가지 값을 비교해본 결과 6을 1로 만들기 위한 최소 연산횟수는 2임을 알 수 있다.

 

3. 예를 들어 N이 10일 경우, 10을 1로 만드는데 필요한 최소 연산 횟수는 아래 세 가지 경우에서 연산 횟수 중 최소값을 구해야 한다.

첫 번째 연산이 -1일 경우 => 1로 만들기 위한 최소 연산 횟수(= dp[9]) + 1 = 2 + 1 = 3
첫 번째 연산이 /2일 경우 => 1로 만들기 위한 최소 연산 횟수(= dp[5]) + 1 = 3 + 1 = 4
첫 번째 연산이 /3일 경우 => 10을 3으로 나눌 수 없으므로 이 경우는 제외된다.

=> 세 가지 값을 비교해본 결과 10을 1로 만들기 위한 최소 연산횟수는 3임을 알 수 있다.

** 즉, f(N)값을 구하기 위해서는 f(2) ~ f(N-1) 값이 앞서 구해져야 한다. => BottomUp 방식
결국, 이 문제는 "N을 1로 만드는 최소 연산 횟수" 라는 Problem을 2~N까지의 Sub Problem들로 쪼개는 DP 문제이다.