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
방법 1: Top-down
|
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
|
import java.io.*;
public class Main {
public static int[] result;
public static void main(String[] args) {
try {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int iCaseCount = Integer.parseInt(br.readLine());
result = new int[11];
calculate(10);
while (iCaseCount-- > 0) {
int temp = Integer.parseInt(br.readLine());
bw.write(result[temp] + "\n");
bw.flush();
}
} catch (Exception e) {
e.printStackTrace();
}
}
public static int calculate(int num) {
if (result[num] > 0) {
return result[num];
}
if (num <= 0) {
return 0;
} else if (num == 1) {
result[1] = 1;
return 1;
} else if (num == 2) {
result[2] = 2;
return 2;
} else if (num == 3) {
result[3] = 4;
return 4;
}
result[num] = calculate(num - 1) + calculate(num - 2) + calculate(num - 3);
return result[num];
}
}
Colored by Color Scripter
|
c++소스
더보기
더보기
|
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;
const int MAX = 10;
int D[MAX + 1] = {1, };
// 점화식 : D[n] = D[n - 1] + D[n - 2] + D[n - 3]
int get_123_sum(int n)
{
if (D[n] > 0)
{
return D[n];
}
if (n <= 2)
{
return D[n] = n;
}
return D[n] = get_123_sum(n - 1) + get_123_sum(n - 2)+ get_123_sum(n - 3);
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int cnt;
cin >> cnt;
while (cnt--)
{
int n;
cin >> n;
get_123_sum(n);
cout << D[n] << '\n';
}
return 0;
}
Colored by Color Scripter
|
방법 2: Bottom-up
|
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
|
import java.io.*;
public class Main {
public static int[] result;
public static void main(String[] args) {
try {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int iCaseCount = Integer.parseInt(br.readLine());
result = new int[11];
result[1] = 1;
result[2] = 2;
result[3] = 4;
for (int i = 4; i <result.length; i++) {
result[i] = result[i - 1] + result[i - 2] + result[i - 3];
}
while (iCaseCount-- > 0) {
int temp = Integer.parseInt(br.readLine());
bw.write(result[temp] + "\n");
bw.flush();
}
} catch (Exception e) {
e.printStackTrace();
}
}
}
Colored by Color Scripter
|
c++소스
더보기
더보기
|
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
|
#include <iostream>
using namespace std;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
const int MAX = 10;
int D[MAX + 1] = { 1, 1, 2, };
// 점화식 : D[n] = D[n - 1] + D[n - 2] + D[n - 3]
for (int i = 3; i <= MAX; i++)
{
D[i] = D[i - 1] + D[i - 2] + D[i - 3];
}
int cnt;
cin >> cnt;
while (cnt--)
{
int n;
cin >> n;
cout << D[n] << '\n';
}
return 0;
}
Colored by Color Scripter
|
또... 바텀업 2 : 1, 2, 3을 더해서 목표 숫자가 되는 가짓수 구하기 (c++)
더보기
더보기
#include <iostream>
using namespace std;
int recurr(int sum, int goal)
{
// 합이 목표 숫자보다 클때 : 불가능한 가짓수
if (sum > goal)
{
return 0;
}
// 합 = 목표 숫자일때 : 가능한 가짓수
else if (sum == goal)
{
return 1;
}
// (1, 2, 3)을 더해서 목표 숫자가 되는 가짓수 구하기
return recurr(sum + 1, goal) + recurr(sum + 2, goal) + recurr(sum + 3, goal);
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int T;
cin >> T;
while (T--)
{
int n;
cin >> n;
cout << recurr(0, n) << '\n';
}
return 0;
}
그리고...
방법 3 : N중 for문 (c++)
더보기
더보기
약간 무서운 소스지만 연습용으로 참고.
잘 쓰일 일이 없는 소스라고 한다. 그럴것 같다.
백준님 강의를 참고하였다.
#include <iostream>
using namespace std;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
const int MAX = 10;
int cnt[MAX + 1] = { 0, };
for (int n = 1; n <= MAX; n++)
{
for (int l1 = 1; l1 <= 3; l1++)
{
if (l1 == n)
{
cnt[n]++;
}
for (int l2 = 1; l2 <= 3; l2++)
{
if (l1 + l2 == n)
{
cnt[n]++;
}
for (int l3 = 1; l3 <= 3; l3++)
{
if (l1 + l2 + l3 == n)
{
cnt[n]++;
}
for (int l4 = 1; l4 <= 3; l4++)
{
if (l1 + l2 + l3 + l4 == n)
{
cnt[n]++;
}
for (int l5 = 1; l5 <= 3; l5++)
{
if (l1 + l2 + l3 + l4 + l5 == n)
{
cnt[n]++;
}
for (int l6 = 1; l6 <= 3; l6++)
{
if (l1 + l2 + l3 + l4 + l5 + l6 == n)
{
cnt[n]++;
}
for (int l7 = 1; l7 <= 3; l7++)
{
if (l1 + l2 + l3 + l4 + l5 + l6 + l7 == n)
{
cnt[n]++;
}
for (int l8 = 1; l8 <= 3; l8++)
{
if (l1 + l2 + l3 + l4 + l5 + l6 + l7 + l8 == n)
{
cnt[n]++;
}
for (int l9 = 1; l9 <= 3; l9++)
{
if (l1 + l2 + l3 + l4 + l5 + l6 + l7 + l8 + l9 == n)
{
cnt[n]++;
}
for (int l0 = 1; l0 <= 3; l0++)
{
if (l1 + l2 + l3 + l4 + l5 + l6 + l7 + l8 + l9 + l0 == n)
{
cnt[n]++;
}
}
}
}
}
}
}
}
}
}
}
}
int T;
cin >> T;
while (T--)
{
int n;
cin >> n;
cout << cnt[n] << '\n';
}
return 0;
}
탑다운보다 바텀업이 근소하게 빨랐다.
TIP1
2 * n 타일링 문제와 원리가 같다.
result[ i ] 가 i 를 1, 2, 3의 합으로 나타내는 방법이라고 했을 때,
result[ i ] = result[ i - 1 ] + result[ i - 2 ] + result[ i - 3 ]
( i - 1 번째에서 1 더하는 경우의 수 ) + ( i - 2 번째에서 2 더하는 경우의 수 ) + ( i - 3 번째에서 3 더하는 경우의 수)
TIP2
|
1
2
3
|
if (num <= 0) {
return 0;
}
|
calculate(num - 3) 을 호출할 때, 매개변수가 음수가 될수도 있으므로
예외처리를 꼼꼼하게 막아주자.
TIP3
문제에서 주어진 최댓값이 11로 매우 작았으므로,
배열의 길이를 12로 선언하고 모든 배열의 값을 먼저 구한 뒤,
테스트 케이스가 주어지면 이미 구한 값을 호출하기만 하는 방식으로 풀이했다.
'Algorithm > BOJ' 카테고리의 다른 글
| [BOJ]16194번: 카드 구매하기 2(java, c++) (0) | 2019.10.15 |
|---|---|
| [BOJ]11052번: 카드 구매하기(java, c++) (0) | 2019.10.14 |
| [BOJ]11727번: 2×n 타일링 2(java, c++) (0) | 2019.10.14 |
| [BOJ]11726번: 2×n 타일링(java, c++) (0) | 2019.10.14 |
| [BOJ]1463번: 1로 만들기(java, c++) (0) | 2019.10.14 |
댓글