백준 문제풀이/SILVER
[백준 / BOJ / SILVER 3] 9095 번 : 1, 2, 3 더하기
지나가던 개발자
2020. 3. 6. 22:55
반응형
https://www.acmicpc.net/problem/9095
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
문제 접근 방법
- 여러가지 방식으로 풀 수 있는 문제입니다.
- n중 for문을 사용하여 구할수도 있고, 재귀를 이용해서도 구할 수 있으며, DP로도 문제를 풀 수 있습니다.
- n중 for문의 경우 값이 일치하는지를 모든 경우에 체크하는 방식으로 진행한다
- 재귀의 경우 맞는 값을 찾았을 경우 정답 출력값의 변수를 증가 시키고 값이 입력 값을 초과했을 경우 return을 해주고, 이 두 경우가 아닐 경우에 각 1, 2, 3 을 더한 함수를 호출하는 방식으로 진행한다.
- DP의 경우에는 점화식을 만들어야 하는데, n을 만들기 위해서 1, 2, 3을 사용하기 때문에 DP[n] = DP[n-1] + DP[n-2] + DP[n-3]가 성립함을 알 수 있다.
아래는 코드입니다.
n중 for문을 사용한 코드입니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
|
#include <iostream>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int testNum, num;
int ary[] = { 1,2,3 };
cin >> testNum;
while (testNum--)
{
int count = 0;
cin >> num;
for (int a = 0; a < 3; a++)
{
if (ary[a] == num)
{
count++;
}
for (int b = 0; b < 3; b++)
{
if (ary[a] + ary[b] == num)
{
count++;
}
for (int c = 0; c < 3; c++)
{
if (ary[a] + ary[b] + ary[c] == num)
{
count++;
}
for (int d = 0; d < 3; d++)
{
if (ary[a] + ary[b] + ary[c] + ary[d] == num)
{
count++;
}
for (int e = 0; e < 3; e++)
{
if (ary[a] + ary[b] + ary[c] + ary[d] + ary[e] == num)
{
count++;
}
for (int f = 0; f < 3; f++)
{
if (ary[a] + ary[b] + ary[c] + ary[d] + ary[e] + ary[f] == num)
{
count++;
}
for (int g = 0; g < 3; g++)
{
if (ary[a] + ary[b] + ary[c] + ary[d] + ary[e] + ary[f] + ary[g] == num)
{
count++;
}
for (int h = 0; h < 3; h++)
{
if (ary[a] + ary[b] + ary[c] + ary[d] + ary[e] + ary[f] + ary[g] + ary[h] == num)
{
count++;
}
for (int i = 0; i < 3; i++)
{
if (ary[a] + ary[b] + ary[c] + ary[d] + ary[e] + ary[f] + ary[g] + ary[h] + ary[i] == num)
{
count++;
}
for (int j = 0; j < 3; j++)
{
if (ary[a] + ary[b] + ary[c] + ary[d] + ary[e] + ary[f] + ary[g] + ary[h] + ary[i] + ary[j] == num)
{
count++;
}
}
}
}
}
}
}
}
}
}
}
cout << count << "\n";
}
return 0;
}
Colored by Color Scripter
|
재귀를 사용한 코드입니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
|
#include <iostream>
using namespace std;
int answer = 0;
void sum(int count, int ans)
{
if (count == ans) {
answer++;
return;
}
else if(count > ans)
{
return;
}
for (int i = 1; i <= 3; i++)
{
sum(count + i, ans);
}
return;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int num;
cin >> num;
while(num--)
{
int a;
cin >> a;
sum(0, a);
cout << answer << "\n";
answer = 0;
}
return 0;
}
Colored by Color Scripter
|
DP를 사용한 코드입니다.
0일 때 아무것도 더하지 않아도 1개가 나오므로 최초값은 1에서 부터 시작하게 하였습니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
#include <iostream>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int a, b;
cin >> a;
while (a--)
{
int check[12] = { 1, };
cin >> b;
for (int i = 1; i <= b; i++)
{
if (i - 1 >= 0)
{
check[i] += check[i - 1];
}
if (i - 2 >= 0)
{
check[i] += check[i - 2];
}
if (i - 3 >= 0)
{
check[i] += check[i - 3];
}
}
cout << check[b] << "\n";
}
return 0;
}
Colored by Color Scripter
|
반응형