티스토리 뷰
반응형
9095번: 1, 2, 3 더하기
각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.
www.acmicpc.net
>문제 설명
더보기
문제
정수 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보다 작다.
출력
각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.
풀이
- 1: 1
- 2: 1+1, 2
- 3: 1+1+1, 1+2, 2+1, 3
- 4: 1+1+1+1, 1+2+1, 2+1+1, 1+1+2, 2+2, 3+1, 1+3
- ...
위에 예시들 처럼 5까지 주르륵 적어두고 규칙을 찾았다.
더할 수 있는 숫자가 1, 2, 3이니 n을 만들 수 있는 방법은 (n-3) + 3, (n-2) + 2, (n-1) + 1 이다.
점화식으로 표현하면 dp엔 방법의 수만 저장하면 되므로, dp[i] = dp[i-3] + dp[i-2] + dp[i-1] 이다.
#define MAXN 11
#include <iostream>
using namespace std;
int t, n;
int dp[MAXN] = {0, };
int main()
{
dp[1] = 1;
dp[2] = 2;
dp[3] = 4;
cin>>t;
for(int i=0; i<t; i++){
cin>>n;
for(int i=4; i<=n; i++){
if(dp[i] == 0){
dp[i] = dp[i-3] + dp[i-2] + dp[i-1];
}
}
cout<<dp[n]<<"\n";
}
return 0;
}
반응형
'CS > Algorithm' 카테고리의 다른 글
[백준-삼성SW역량테스트 기출] 14890번. 경사로 C++ (0) | 2021.03.10 |
---|---|
[백준] 10844번. 쉬운 계단 수 C++ (0) | 2021.03.10 |
[백준] 11727번. 2×n 타일링 2 C++ (0) | 2021.03.09 |
[백준] 11726번. 2×n 타일링 C++ (0) | 2021.03.09 |
[백준] 1463번. 1로 만들기 C++ (0) | 2021.03.09 |
댓글
반응형
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- DP
- 백준
- Android
- beakjoon
- BFS
- error
- rn
- 구현
- algorithm
- react navigation
- 일기
- DFS
- 삼성SW역량테스트 기출
- C++
- 시뮬레이션
- Problem Solving
- 삼성sw역량테스트
- 웨이팅후기
- 기출
- react-native-make
- 알고리즘
- 지킬앤하이드
- 브루트포스 알고리즘
- application
- typescript
- react native
- 하단탭
- react-native
- problem
- 뉴욕여행
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
글 보관함