9095번: 1, 2, 3 더하기
문제 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다. 출력 각
www.acmicpc.net
이 문제는 두 가지 방법으로 풀어봤다.
풀이 1 ) 완전 탐색
a1, a2, a3에 각각 1, 2, 3의 개수를 저장한 후 그 3가지의 순서 개수를 구했다. 팩토리얼을 구하는 라이브러리 함수가 없으므로 내가 만들었다. 물론 여기서 팩토리얼을 구할 때 재귀 호출이 아닌 dp를 사용하여 구할 수도 있지만 문제에서 주어진 n의 크기가 작으므로 재귀 호출로 구해주었다.
단 이 때는 팩토리얼의 크기가 int범위를 벗어나지 않는지 확인해줄 필요가 있다. 12! 까지 int로 표현 가능하고 13! 부터는 long long형을 사용하면 되는데 그냥 long long형을 사용하는 게 더 편한 것 같다.
#include <cstdio>
using namespace std;
int fac(int);
int main(void)
{
int t;
scanf("%d", &t);
while(t--){
int n;
int ans = 0;
scanf("%d", &n);
int a1, a2, a3;
for(a3 = 0; a3*3 <= n; a3++){
for(a2 = 0; a3*3 + a2*2 <= n; a2++){
a1 = n - a3*3- a2*2;
ans += fac(a1+a2+a3)/fac(a1)/fac(a2)/fac(a3);
}
}
printf("%lld\n", ans);
}
return 0;
}
int fac(int n)
{
if(n < 2) return 1;
else return n*fac(n-1);
}
풀이 2 ) dp
n을 1, 2, 3으로 나타내는 방법은 다시 보면 1로 시작하는 경우와 2로 시작하는 경우와 3으로 시작하는 경우 3가지로 나눌 수 있다. 1로 시작하는 경우는 1과 n-1로 나누고 2, 3도 같은 방식으로 나눌 수 있다. 즉 n을 1, 2, 3으로 나타내는 방법의 수를 f(n)이라 했을 때 f(n) = f(n-1) + f(n-2) + f(n-3)으로 나타낼 수 있다.
위의 식을 재귀로 구할 수도 있지만 dp를 사용하여 구했다.
#include <cstdio>
using namespace std;
int memo[12] = {1, 2, 4, };
int main(void)
{
int t;
scanf("%d", &t);
while(t--){
int n;
scanf("%d", &n);
for(int i = 3; i < n; ++i)
memo[i] = memo[i-1] + memo[i-2] + memo[i-3];
printf("%d\n", memo[n-1]);
}
return 0;
}
'문제풀이 > 백준' 카테고리의 다른 글
| [C++] 백준 - 10973 : 이전 순열 (0) | 2020.03.12 |
|---|---|
| [C++] 백준 - 10972 : 다음 순열 (0) | 2020.03.12 |
| [C++] 백준 - 14500 : 테트로미노 (0) | 2020.03.11 |
| [C++] 백준 - 1476 : 날짜 계산 (0) | 2020.03.10 |
| [C++] 백준 - 2309 : 일곱 난쟁이 (0) | 2020.03.10 |
