BOJ_1로만들기_1463

이번 포스팅에서는 1로만들기 1463번 문제를 풀어보려 합니다.

Dynamic Programming의 기본 문제라고 보시면 됩니다.

문제는 아래와 같습니다.

DP문제는 조건을 먼저 확인해야 합니다.

이유는 조건에 따라서 점화식이 세워지기 때문입니다.

조건 

1. 3으로 나누어 떨어지면 3으로 나눈다.

2. 2로 나누어 떨어지면 2로 나눈다.

3. 1을 뺀다.

D[n] 은 n이라는 수에서 나올 수 있는 경우의 수라고 한다면,

3으로 나누어 떨어지면 3으로 나눈다는 것은 n/3이 될 것이고

2로 나누어 떨어지면 2로 나눈다는 것은 n/2가 될 것입니다.

마찬가지로 1을 빼는 것은 n-1이 됩니다.

따라서 n이 3으로 나누어 떨어질 경우 D[n] = D[n/3] + 1 이 됩니다. (경우의 수)

마찬가지로 n이 2로 나누어 떨어질 경우는 D[n] = D[n/2] + 1 이 됩니다.

1을 빼는 것은 d[n] = d[n-1] + 1이 됩니다.

이러한 점화식을 토대로 코드를 짜면 다음과 같습니다.

---

for (int i = 2; i <= N; i++) {

d[i] = d[i - 1] + 1;

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

d[i] = d[i / 3] + 1;

}

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

d[i] = d[i / 2] + 1;

}

}

---

그리고 DP문제는 초기값이 중요하기 때문에 d[0] = 0 , d[1] = 0 이라고 잡아줘야 합니다.

n이라는 값을 1로 만드는 것이기 때문에 n이 0이나 1일 경우는 그 경우의 수가 0일 수 밖에 없다.

전체 코드는 다음과 같습니다.

---

import java.util.Scanner;

public class 일로만들기_2번 {

private static Scanner scanner;

private static int[] d;

public static void main(String[] args) {

// TODO Auto-generated method stub

scanner = new Scanner(System.in);

int N = scanner.nextInt();

d = new int[N + 1];

d[0] = 0;

d[1] = 0;

for (int i = 2; i <= N; i++) {

d[i] = d[i - 1] + 1;

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

d[i] = d[i / 3] + 1;

}

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

d[i] = d[i / 2] + 1;

}

}

System.out.println(d[N]);

}

}

---

감사합니다.