250x250
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 | 31 |
Tags
- 딥러닝
- exists
- AlexNet
- DP
- SIFT
- MySQL
- edge detection
- canny edge detection
- 그래프 이론
- IN
- Mask Processing
- sklearn
- MinHeap
- 인공지능
- C++
- classification
- Python
- Reinforcement Learning
- 강화학습
- BFS
- object detection
- 머신러닝
- image processing
- dfs
- 백준
- clustering
- TD
- machine learning
- opencv
- dynamic programming
Archives
- Today
- Total
JINWOOJUNG
[ DP - 9095 ] 1, 2, 3 더하기 본문
728x90
반응형
접근법
직접 해 보는 것이 DP문제에서 규칙을 찾는 가장 쉬운 방법인 것 같다.
- 1 표현
- 1
- 2 표현
- 1+1
- 2
- 3 표현
- 1+1+1
- 1+2
- 2+1
- 3
1,2,3은 각각 1,2,4가지로 표현 가능하다.
4를 1,2,3의 합으로 나타내보자.
- 1+1+1+1
- 1+1+2
- 1+2+1
- 1+3
- 2+2
- 2+1+1
- 3+1
총 7가지인데, 처음이 1일 때 나머지 3을 나타낼 수 있는 가지수는 위에서 구한 4가지, 처음이 2일 때 나머지 2를 나타낼 수 있는 가지수는 2가지 그리고 처음이 1이면 1가지 이다.
따라서 DP[4] = DP[4-1] + DP[4-2] + DP[4-3] 으로 표현 가능하다. 이제 구현해보자.
정답
#include<iostream>
#include<vector>
using namespace std;
int32_t DP[12];
int main()
{
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int32_t s32_I, s32_T, s32_J;
cin >> s32_T;
vector<int32_t> st_Reuslt;
for (s32_I = 0; s32_I < s32_T; s32_I++)
{
cin >> s32_J;
st_Reuslt.push_back(s32_J);
}
DP[1] = 1;
DP[2] = 2;
DP[3] = 4;
for (s32_I = 4; s32_I <= 11; s32_I++)
{
DP[s32_I] = DP[s32_I - 1] + DP[s32_I - 2] + DP[s32_I - 3];
}
for (s32_I = 0; s32_I < s32_T; s32_I++)
{
cout << DP[st_Reuslt[s32_I]] << endl;
}
return 0;
}
728x90
반응형
'백준' 카테고리의 다른 글
[ DP - 1149 ] RGB거리(C++) (0) | 2024.03.31 |
---|---|
[ DP - 1003 ] 피보나치 함수 (0) | 2024.03.30 |
[ DP - 1463 ] 1로 만들기(C++) (0) | 2024.03.25 |
[ DP - 2839 ] 설탕 배달(C++) (0) | 2024.03.24 |
[ 28217 ] 두 정삼각형(C++) (0) | 2024.03.24 |