일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- 수학
- 그리디
- 프로그래머스
- 정수론
- 정렬
- C언어
- 다이나믹프로그래밍
- C
- 프로그래머스연습문제
- 브루트포스알고리즘
- 프로그래머스코딩테스트
- 그리디알고리즘
- 이분탐색
- 논문구현
- 해시를사용한집합과맵
- Image Classification
- 프로그래머스sql
- 사칙연산
- 백준
- 소수판정
- 논문리뷰
- 백준알고리즘
- MySQL
- C++
- 자료구조
- 큐
- 이진탐색
- SQL
- 문자열
- 구현
- Today
- Total
초보 개발자의 이야기, 릿허브
[C++] 백준 9095번 1, 2, 3 더하기 본문
1. 문제이해
9095번: 1, 2, 3 더하기 (acmicpc.net)
9095번: 1, 2, 3 더하기
각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.
www.acmicpc.net
정수가 주어졌을 때, 해당 정수를 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 것이 목표이다.
2. 문제풀이
정수 N이 주어지고, 해당 정수를 1, 2, 3으로 나타낼 수 있는 경우의 수를 출력해야한다.
주의해야 할 점은 숫자를 반드시 1, 2, 3 의 합으로만 나타내야 한다는 것이다.
또한, 위의 정수 4에 대한 예제 풀이로 보았을 때,
순서를 바꿔 더하는 경우도 다른 경우로 포함시켜야 함을 알 수 있다.
(위의 예제에서 1+1+2, 1+2+1을 다른 경우로 세어준 경우)
따라서, 이에 유의해서, 1부터 5까지의 숫자를 1, 2, 3의 합으로 나타내어 보면
다음과 같은 결과를 얻을 수 있다.
위 그림을 보면, 4부터 일정한 규칙에 따라 1, 2, 3의 합으로 나타내어지는 것을 확인할 수 있다.
4의 경우에는,
결괏값은
3(4-1)의 경우의 수들 + 1
2(4-2)의 경우의 수들 + 2
1(4-3)의 경우의 수들 +3
개수는
3(4-1)의 경우의 수들 + 2(4-2)의 경우의 수들 + 1(4-3)의 경우의 수들
이 나왔다.
또 다른 경우인 5의 경우에는,
결괏값은
4(5-1)의 경우의 수들 + 1
3(5-2)의 경우의 수들 + 2
2(5-3)의 경우의 수들 +3
개수는
4(5-1)의 경우의 수들 + 3(5-2)의 경우의 수들 + 2(5-3)의 경우의 수들
이 나왔다.
(1의 경우의 수들의 경우에는 1+4로, 1, 2, 3의 합이 아니기 때문에 제외)
따라서, 정수 N을 1, 2, 3의 합으로 나타낼 수 있는 가짓수는
(N-1)의 경우의 수 + (N-2)의 경우의 수 + (N-3)의 경우의 수 가 된다.
(우리가 구하는 것은 결과값이 아니라 경우의 수의 개수이다!)
이를 재귀를 통해 아래와 같은 코드로 구현해보았다.
3. 소스코드
#include <iostream>
using namespace std;
int add(int n) {
if (n == 1) { // 정수가 1인 경우
return 1;
}
else if (n == 2) { // 정수가 2인 경우
return 2;
}
else if (n == 3) { // 정수가 3인 경우
return 4;
}
// 정수 N을 1, 2, 3 의 합으로 나타낼 수 있는 경우의 수는
// (N-1)의 경우의 수 + (N-2)의 경우의 수 + (N-3)의 경우의 수
return add(n - 1) + add(n - 2) + add(n - 3);
}
int main() {
int T; // 테스트 케이스의 개수
int arr[10000]; // 각 테스트 케이스의 정수
int result[10000]; // 1, 2, 3의 합으로 나타낼 수 있는 경우의 수
cin >> T;
for (int i = 0; i < T; i++) {
cin >> arr[i]; // 정수를 입력받아
result[i] = add(arr[i]); // 경우의 수를 계산하여 result 배열에 넣기
}
for (int i = 0; i < T; i++) {
cout << result[i] << '\n';
}
return 0;
}
함수를 따로 구현하여 2. 문제풀이의 방식대로 코드를 구현했다.
테스트 케이스의 개수(T)와 각 정수들(arr[i])을 입력받아, add 함수를 통해 경우의 수를 계산하고,
계산한 값을 result[i] 배열에 넣어 이를 다시 출력해주었다.
add 함수의 경우에는,
들어온 정수가 1, 2, 3인 경우에는 바로 해당 경우의 수를 반환하고,
아닌 경우에는 (N-1)의 경우의 수 + (N-2)의 경우의 수 + (N-3)의 경우의 수를 구해
반환하도록 구현했다.
역시 무슨 문제이던지 간에 써보고 푸는게 제일인 것 같다..
한참 들여다보고 풀려고 할때는 안풀리더니,
노트에 이래저래 써보고 하니 금방 규칙을 찾을 수 있었던 문제였다.
혹여나 궁금한 점이나 이해가 안되는 점이 있다면 언제든지 댓글은 환영입니다.🤗
'코딩테스트 > 📗 백준 (BOJ)' 카테고리의 다른 글
[C++] 백준 1057번 토너먼트 (0) | 2021.09.13 |
---|---|
[C++] 백준 10866번 덱 (0) | 2021.09.12 |
[C++] 백준 12845번 모두의 마블 (0) | 2021.09.09 |
[C++] 백준 1003번 피보나치 함수 (0) | 2021.09.08 |
[C++] 백준 20115번 드링크 (0) | 2021.09.03 |