[알고리즘] 1463번, 1로 만들기 JAVA풀이
1463번, 1로 만들기 JAVA풀이
- 세준이는 어떤 정수 N에 다음과 같은 연산중 하나를 할 수 있다
- N이 3으로 나누어 떨어지면, 3으로 나눈다.
- N이 2로 나누어 떨어지면, 2로 나눈다.
- 1을 뺀다.
- 12의 경우
- 12 / 3 = 4
- 4 / 2 = 2
- 2 - 1 = 1
- 10의 경우 (1)
- 10 / 2 = 5
- 5 - 1 = 4
- 4 / 2 = 2
- 2 - 1 = 1
- 10의 경우 (2)
- 10 - 1 = 9
- 9 / 3 = 3
- 3 / 3 = 1
- D[N] = N을 1로 만드는데 필요한 연산의 최솟 값
- N에서 3로 나눴을 경우
- N -> N/3 까지의 계산횟수는 1번
- 즉, D[N] = D[N/3] + 1
- N에서 2로 나눴을 경우
- N -> N/2 까지의 계산횟수는 1번
- 즉, D[N] = D[N/2] + 1
- N에서 1을 뺐을 경우
- N -> N-1 까지의 계산횟수는 1번
- 즉, D[N] = D[N-1] + 1
// TOP-DOWN
int go (int n) {
if (n == 1) return 0;
if (d[n] > 0) return d[n];
d[n] = go(n-1) + 1;
if (n%2 == 0) {
int temp = go(n/2) + 1;
if (d[n] > temp) d[n] = temp;
}
if (n%3 == 0) {
int temp = go(n/3) + 1;
if (d[n] > temp) d[n] = temp;
}
return d[n];
}
D[N] 을 전부 채우는데 N개가 필요함 * 1칸을 채우는데 걸리는 비용 = N * O(1)
O(1)
- go(n-1) + 1
- go(n/2) + 1
- go(n/3) + 1
// Bottom-up
public static int bottomUp (int n) {
d[1] = 0;
for (int i=2; i<=n; i++) {
d[i] = d[i-1] + 1;
if (i%2 == 0 && d[i] > d[i/2] + 1) {
d[i] = d[i/2] + 1;
}
if (i%3 == 0 && d[i] > d[i/3] + 1) {
d[i] = d[i/3] + 1;
}
}
return d[n];
}
