0%

[백준/1463] 1로 만들기

작성일 Edited on In Disqus:

Baekjoon Online Judge - 1463

Review

인덱스 횟수
1 0
2 1
3 1

위 테이블을 보면, 1은 만들 필요가 없으니까 0, 2와 3은 2로 3으로 나누어 떨어지고, 몫이 1이 나오니까 횟수가 1이다. 그렇다면 4부터는 어떻게 구할까?

| 인덱스 | 횟수 |
| 4 | 3, 1 또는 2, 1 |

4를 1로 만드는 최솟값을 구해야 하는 경우, 4를 1로 뺐을 때 3이 되고, 3의 값은 1이므로 총 두 번이 된다. 하지만 4를 2로 나누는 경우 몫이 2가 되는데, 2의 값은 1이므로 3으로 나누었을 때와 마찬가지로 총 두 번이 된다. 이러나저러나 4를 1로 만드는 최솟값은 2가 되는 것이다.

| 인덱스 | 횟수 |
| 5 | 4, 3, 1 또는 4, 2, 1 |

다시 5를 예로 들자면, 5는 3이나 2로 나누어 떨어지지 않으므로 무조건 1을 빼고 시작해야 한다. 5-1=4인데, 4의 횟수는 아까 구한 2이다. 따라서 5의 최솟값은 4의 연산 횟수(2) + 빼기 연산(1) = 3이 된다.

이렇게 10까지 반복하면 아래와 같은 테이블이 만들어지게 된다.

인덱스 횟수
1 0
2 1
3 1
4 3, 1 또는 2, 1
5 4, 3, 1
6 3, 1 또는 2, 1
7 6, 3, 1
8 4, 3, 1
9 3, 1
10 9, 3, 1

각 인덱스의 최솟값을 담은 배열을 A라고 했을 때, 점화식은 다음과 같다.

  • 1을 뺐을 때: A[n - 1] + 1
  • n % 2 == 0일 때: A[n / 2 == 0] + 1
  • n % 3 == 0일 때: A[n / 3 == 0] + 1

횟수를 계산해야 하기 때문에 1을 더한다. 각 케이스의 값을 비교해 최소값을 찾아내서 A[n] 배열에 넣어주면 된다.

Code (JAVA) - Bottom-up

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int[] arr = new int[n + 1];
    arr[0] = arr[1] = 0;

    for(int i = 2; i <= n; i++) {
      arr[i] = arr[i - 1] + 1;

      if(i % 2 == 0 && arr[i] > arr[i / 2] + 1) {
        arr[i] = arr[i / 2] + 1;
      }

      if(i % 3 == 0 && arr[i] > arr[i / 3] + 1) {
        arr[i] = arr[i / 3] + 1;
      }

    }
    System.out.println(arr[n]);
    sc.close();
  }
}

Code (JAVA) - Top-down

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
import java.io.*;

public class Main {
  
  static int[] dp;
  
  public static int dp(int n) {
    if(n <= 1) {
      return 0;
    } else if(dp[n] != 0) {
      return dp[n];
    } else {
      dp[n] = dp(n - 1) + 1;
      if(n % 3 == 0 && dp[n] > dp(n / 3) + 1) {
        dp[n] = dp(n / 3) + 1;
      }
      if(n % 2 == 0 && dp[n] > dp(n / 2) + 1) {
        dp[n] = dp(n / 2) + 1;
      }

    }
    return dp[n];
  }
  
  public static void main(String args[]) throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int N = Integer.parseInt(br.readLine());
    dp = new int[N + 1];
    System.out.println(dp(N));

  }
}

Code (Javascript)

  • 역시 백준에서 자바스크립트 입력은… 노우…
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var fs = require('fs');
var input = fs.readFileSync('/dev/stdin').toString().split("\n");
var X = parseInt(input[0]);

// 1부터 3까지의 값을 미리 넣어준다.
// 편의를 위해 인덱스는 1부터 시작한다
let dp = [0, 0, 1, 1];

for (let i = 4; i <= X; i++) {
  // -1을 뺄 때, 2로 나눌 때, 3으로 나눌 때의 값을 비교해 최소값을 알아냄
  // -1을 했을 때
  dp[i] = dp[i - 1] + 1;
  // 3으로 나누어 떨어지는 수일 때
  if (i % 3 === 0) dp[i] = Math.min(dp[i], dp[i / 3] + 1);
  // 2로 나누어 떨어지는 수일 때
  if (i % 2 === 0) dp[i] = Math.min(dp[i], dp[i / 2] + 1);
}

console.log(dp[X])