문제

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

풀이

처음 동적계획법을 공부할때 어렵게 풀었던 문제이지만, 실제로는 상당히 쉬운 난이도의 문제이다.

문제는 1, 2, 3만 사용한 합으로 어떤 수 N을 만들 수 있는 모든 경우의 수를 구하는 것이 목적이다. 여기서 우리는 N ≤ 3 또는 그 보다 약간 큰 수일때 경우의 수를 쉽게 구해볼 수 있다. 여기서는 5까지 한번 구해보도록 하겠다.

N = 1

  • 1

N = 2

  • 1 + 1
  • 2

N = 3

  • 1 + 1 + 1
  • 1 + 2
  • 2 + 1
  • 3

N = 4

  • 1 + 1 + 1 + 1
  • 2 + 1 + 1
  • 1 + 2 + 1
  • 1 + 1 + 2
  • 2 + 2
  • 1 + 3
  • 3 + 1

N = 5

  • 1 + 1 + 1 + 1 + 1
  • 1 + 1 + 1 + 2
  • 1 + 1 + 2 + 1
  • 1 + 2 + 1 + 1
  • 2 + 1 + 1 + 1
  • 1 + 1 + 3
  • 1 + 3 + 1
  • 3 + 1 + 1
  • 3 + 2
  • 2 + 3
  • 2 + 2 + 1
  • 2 + 1 + 2
  • 1 + 2 + 2

우리는 경우의 수를 구해야 하므로 경우의 수만 보도록 하자. N ≤ 3일때는 규칙이 없지만, N > 3일 경우에는 규칙을 찾을 수 있다. 이는 상당히 단순한 식으로 구할 수 있는데 f(N) = N을 1, 2, 3의 합으로 나타낼 수 있는 경우라 할때 f(N) = f(N-1) + f(N-2) + f(N-3) when N > 3라는 것이다. 즉 N - 1을 만들 수 있는 모든 식에 1을 더하면 N이 되고 N - 2를 만들 수 있는 모든 식에 2를, N - 3을 만들 수 있는 모든 식에 3을 더하면 N이 되므로 이 모든 경우를 다 합치면 N을 만들 수 있는 경우가 된다. 아래는 문제를 해결하는 식을 구현한 코드인데 N ≤ 3인 경우에는 규칙이 없으므로 메모이제이션 배열에 직접 값을 대입하였다.

코드

#include<stdio.h>
#define INT_MAX 987654321
int r[1000001];
int min(int x,int y) {return x<y?x:y;}
int solve(int x){
 	if(r[x] != INT_MAX) return r[x];
 	if(x%3==0) r[x] = solve(x/3);
 	if(x%2==0) r[x] = min(r[x], solve(x/2));
	r[x] = min(r[x], solve(x-1))+1;
	return r[x];
}
int main(){
	int n,i;
    scanf("%d",&n);
	for(i=0;i<=n;i++) r[i] = INT_MAX;
	r[1] = 0;
	r[2] = 1;
	r[3] = 1;
	printf("%d", solve(n));
}