[BOJ][C++] 1463번 1로 만들기(feat. DP)

[문제]

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

정수 x 가 주어졌을 때, x 를 1로 만드는 최소 연산의 수를 찾는 문제이다.

 

x 를 1로 만드는 연산은 3가지가 있다.

 

1) x 가 3 으로 나누어 떨어지면 x 를 3 으로 나눈다.

2) x 가 2 로 나누어 떨어지면 x 를 2 로 나눈다.

3) 1)2) 가 아니면 x 에서 1을 뺀다.

 

정수 x 값의 범위는 1 ≤ x ≤ 10^6 이다.

제한시간은 0.15초 이다.

 

[풀이]

정수 x 의 최대값이 10^6 이기 때문에 O(n^2) 만 되어도 문제의 제한시간을 넘긴다. 즉, 완전탐색으로 풀면 안된다.

 

점화식을 찾아야 한다.

'D[x] = x를 1로 만드는 최소 연산의 수' 라고 두고 D[1] 부터 구해보자.

 

D[1] = 1

D[2] = D[2/2] = 1

D[3] = D[3/3] = 1

D[4] = D[4/2] = D[2] = D[2/2] = 1

 

D[4] 까지만 구해봐도 D[2] 를 재사용함을 알 수 있다.

큰 값 x를 작은 값들을 이용해서 풀 수 있는 문제. DP 알고리즘으로 풀 수 있다.

 

따라서 D[x] 의 점화식은 D[x] = min(D[x/3] + 1, D[x/2] + 1, D[x-1] + 1) = min(D[x/3], D[x/2], D[x-1]) + 1 이다.

다만, x가 3으로 나누어떨어지는 경우, 2로 나누어떨어지는 경우, 3이나 2로 나누어 떨어지지 않는 경우까지 총 3가지 경우가 존재하므로 나눠서 최소값을 구해야 한다.

 

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) d[n] = min(d[n], go(n/2) + 1);
    if(n%3 == 0) d[n] = min(d[n], go(n/3) + 1);

    return d[n];
}

시간복잡도: O(n)

 

2) Bottom-up 방식

d[1] = 0;
for(int i = 2; i<= n; i++){
    d[i] = d[i-1] + 1;
    if(i%2 == 0) d[i] = min(d[i], d[i/2] + 1);
    if(i%3 == 0) d[i] = min(d[i], d[i/3] + 1);
}

시간복잡도: O(n)

 

[코드]

//Top-down 방식

#include <iostream>
#include <algorithm>
using namespace std;

const int MAX_SIZE = 1000001;
int d[MAX_SIZE]; // d[x] = x를 1로 만드는 최소 연산의 수.

int go(int x);

int main() {
	int x;

	cin >> x;
	cout << go(x) << "\n";

	return 0;
}

int go(int x) {
	if (x == 1) return 0;
	if (d[x] > 0) return d[x];

	d[x] = go(x - 1) + 1;
	if (x % 3 == 0) d[x] = min(d[x], go(x / 3) + 1);
	if (x % 2 == 0) d[x] = min(d[x], go(x / 2) + 1);

	return d[x];
}

 

 

//Bottom-up 방식

#include <iostream>
#include <algorithm>
using namespace std;

int go(int x);

int main() {
	int x;
	
	cin >> x;
	cout << go(x);

	return 0;
}

int go(int x) {
	int* d = new int[x + 1] {0, };

	d[1] = 0;	
	for (int i = 2; i <= x; i++) {
		d[i] = d[i - 1] + 1;
		if (i % 2 == 0) d[i] = min(d[i], d[i / 2] + 1);
		if (i % 3 == 0) d[i] = min(d[i], d[i / 3] + 1);
	}

	return d[x];
}

---

*  DP 개념 및 풀이법 정리

https://i-believe-in-me.tistory.com/413

DP(Dynamic Programming) 개념, 풀이법