Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- HTML #CSS
- BOJ #컴퓨터공학 #C++ #알고리즘 #자료구조
- 컴퓨터공학 #자료구조 #스택 #c++ #알고리즘 #백준문제풀이
- 컴퓨터공학 #Java #자바 #클래스 #객체 #인스턴스
- 컴퓨터공학 #c #c언어 #문자열입력
- 잔
Archives
- Today
- Total
영벨롭 개발 일지
[백준 BOJ][C++]9095번 1, 2, 3 더하기 풀이: DP 본문
https://www.acmicpc.net/problem/9095
이 문제는 Dynamic Programming 을 이용하여 해결할 수 있습니다.
숫자 N | 모든 경우 | 경우의 수 dp[N] |
1 | =1 | 1 |
2 | =1+1 =2 |
2 |
3 | =1+1+1 =1+2 =2+1 =3 |
4 |
4 | =1+3 (3=1+1+1 =1+2 =2+1 =3) =2+2 (2=1+1 =2) =3+1 (1=1) |
7 =dp[1]+dp[2]+dp[3] |
5 | =1+4 (4=1+1+1+1 =1+1+2 =1+2+1 =2+1+1 =2+2 =1+3 =3+1) =2+3 (3=1+1+1 =1+2 =2+1 =3) =3+2 (2=1+1 =2) |
13 =dp[2]+dp[3]+dp[4] |
위 표를 보시면 숫자 N을 1, 2, 3의 합으로 나타내는 경우의 수는 N에서 각각 1, 2, 3을 뺀 값에 대한 수에 대한 경우의 수들의 합입니다.
dp[n]을 숫자 n을 1, 2, 3의 합으로 나타낸 경우의 수라고 하면,
점화식은 dp[n] = dp[n-1] + dp[n-2] + dp[n-3] , (n>3) 이 됩니다.
#include<iostream>
using namespace std;
int dp[11] = { 0, };
int main(void) {
int t, n;
dp[1] = 1;
dp[2] = 2;
dp[3] = 4;
cin >> t;
while (t > 0) {
cin >> n;
if (dp[n] != 0) {
cout << dp[n] << endl;
}
else {
for (int i = 4; i <= n; i++) {
dp[i] = dp[i - 3] + dp[i - 2] + dp[i - 1];
}
cout << dp[n] << endl;
}
t--;
}
return 0;
}
반응형
'알고리즘 문제 풀이 > BOJ' 카테고리의 다른 글
[백준 BOJ][C++]11047번 동전 0 풀이: 그리디 알고리즘 (0) | 2022.02.24 |
---|---|
[백준 BOJ][C++]11399번 ATM 풀이: 그리디 알고리즘 (0) | 2022.02.24 |
[백준 BOJ][C++]1463번 1로 만들기: DP (0) | 2022.02.24 |
[백준 BOJ][C++]2004번: 조합 0의 개수 풀이 (0) | 2022.02.22 |
[백준 BOJ][C++]1676번: 팩토리얼 0의 개수 풀이 (0) | 2022.02.22 |