[백준/C++]#1463 - 1로 만들기

풀이

#include <iostream>
using namespace std;

int D[1000000];		// 함수 값 저장하기 위한 배열 정의
int makeone(int n) {
	if (n == 1) return 0;		// n이 1일 때 0 값 반환
	if (D[n] > 0) return D[n];	// 배열 값이 존재할 때 배열 값 반환
	D[n] = makeone(n-1) + 1;
	if (n % 2 == 0) {	// 2로 나눠지면서 n/2가 더 작은 경우였다면 D[n]에 저장
		if (makeone(n-1) > makeone(n/2)) D[n] = makeone(n/2)+1;
	}
	if (n % 3 == 0) {	// 3으로 나눠지면서 n/3이 더 작은 경우였다면 D[n]에 저장
		if (makeone(n-1) > makeone(n/3)) D[n] = makeone(n/3)+1;
	}
	return D[n];
}

int main() {
	int k;
	cin >> k;
	cout << makeone(k);
	return 0;
}

알고리즘 개념

이 문제는 다이나믹 프로그래밍 문제라고 불린다.

특유의 성질이 있는데, 큰 문제는 작은 문제로 나눠지며 풀이는 동일하다. 그리고 문제의 정답을 작은 문제의 정답에서 구할 수 있다.

이 때 재귀호출을 사용하는데, 오버헤드가 큰 단점이 있다. 그러한 점을 완화하기 위해 중복호출을 제거해준다. 다이나믹 프로그래밍 문제는 다시 풀어도 동일한 결과가 나오므로, 한번 계산할 때 배열에 값을 대입한다!

---

풀이 

n이 1이 되는데 필요한 최소 계산의 수는 D[n]이다. D[n]은 

①D[n/3] + 1

②D[n/2] + 1

③D[n-1] + 1

이렇게 3개 중 최소값을 가지는 하나이다.

if문을 통해 비교하고, 가장 작은 값을 리턴하면 된다.

makeone() 함수를 만들어서 사용한다. 이 함수는 재귀함수이므로, 순환이 끝나는 부분이 존재해야한다.

n이 1일 때, 1이 되는데는 계산이 필요하지 않으므로 D[1] 은 0이다. 이 경우를 if로 나눠서 return 0을 한다.

그리고 이전 계산을 통해 D[n]에 값이 저장되어 있다면 if문을 통해 D[n]>0인 경우를 찾아서 중복호출을 방지할 수 있다.

새로운 호출이면, 일단 D[n]을 ③에 대입한다. 그리고 n이 2로 나눠지면서 makeone(n-1)>makeone(n/2) 이면 D[n]에 ②를 저장한다.

그 다음, n이 3으로 나눠지며 makeone(n-1)>make(n/3) 이면 D[n]에 ①을 저장한다.

이러한 과정을 거치면서 ①②③이 반복되므로 D[n]에 최소값이 저장된다.

 

---

+a

 

위는 Top-Down 방식인데, Down-Top 방식으로도 문제를 해결할 수 있다. n을 줄여서 1로 만드는게 아닌, 1에서 시작해 n으로 늘리는 방식이다. 

다음은 Down-Top방식이면서, 반복문을 사용한 코드이다.

#include <iostream>
using namespace std;

int d[1000001];
int main() {
    int n;
    cin >> 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;
        }
    }
    cout << d[n];
    return 0;
}