난이도 : 실버3
소요시간 : 23m
사용한 풀이법 : DP
풀이 과정
- dp[1] = 1 => 1 dp[2] = 1+1, 2 => 2 dp[3] = 1+1+1, 1+2, 2+1, 3 => 4 dp[4] = 1+1+1+1, 1+1+2, 1+2+1, 1+3, 2+1+1, 2+2, 3+1 => 7
- 위의 식을 잘 보면 1로 시작하는 건 곧 1+3 인거라서 3을 이루는 덧셈의 경우의 수, 즉 dp[3]만 알면 됨 2로 시작하는건 2+2라서 dp[2]만 알면되고 3으로 시작하는건 dp[1]만 알면 됨.
- dp[5]를 예시로 들어보자
- 1+…. 일때는 4를 이루는 경우들만 알면 됨 ⇒ dp[4] == dp[5-1]
- 2+…. 일때는 3을 이루는 경우들만 알면 됨 ⇒ dp[3] == dp[5-2]
- 3+…. 일때는 2를 이루는 경우들만 알면 됨 ⇒ dp[2] == dp[5-3]
- 즉 dp[n] = dp[n-1]+dp[n-2]+ dp[n-3] 이라는 아주 간단한 점화식 완성!!
작성 코드
#include <iostream>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
int dp[12];
dp[1]=1;
dp[2]=2;
dp[3]=4;
for(int i=4; i<12; i++){
dp[i] = dp[i-1]+dp[i-2]+dp[i-3];
}
while(t--){
int n;
cin >> n;
cout << dp[n]<<'\n';
}
}
'알고리즘' 카테고리의 다른 글
백준 #1699 <제곱수의 합> (0) | 2024.03.09 |
---|---|
백준 #1463 <1로 만들기> (0) | 2024.03.08 |
백준 #1932 (0) | 2024.03.03 |
백준 #1260 (0) | 2024.03.03 |
백준 #1182 부분 수열의 합 (1) | 2024.02.12 |