[백준/BOJ] 9095번 - 1, 2, 3 더하기 (C++)

문제 링크

 

코딩하기 전 생각하기

/*
1. 테이블 정의하기
    D[i] = i를 1, 2, 3의 합으로 나타내는 방법의 수
2. 점화식 찾기
    D[3] : (3을 1, 2, 3의 합으로 나타내는 방법) 4개
    D[2] : (2를 1, 2, 3의 합으로 나타내는 방법) 2개
    D[1] : (1를 1, 2, 3의 합으로 나타내는 방법) 1개
    D[4] = D[1] + D[2] + D[3]
    D[i] = D[i-1] + D[i-2] + D[i-3]
3. 초기값 정하기
    D[1] = 1, D[2] = 2, D[3] = 4
*/

 

---

 

코드

#include <bits/stdc++.h>
using namespace std;

int d[20];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    d[1] = 1; d[2] = 2; d[3] = 4;
    for (int i = 4; i < 11; i++)
        d[i] = d[i-1] + d[i-2] + d[i-3];

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        cout << d[n] << '\n';
    }
}

 

---

 

느낀점

 

바킹독님의 강의를 들으면서 요즘 핫한 DP에 대해서 공부해보았다.

https://blog.encrypted.gg/974?category=773649 

[실전 알고리즘] 0x10강 - 다이나믹 프로그래밍

DP 문제를 풀 때 3가지를 기억하자.

1. 테이블 정의하기

2. 점화식 찾기

3. 초기값 정하기

 

(주의) 기록용으로 작성한 글입니다. 코드가 허접하거나 알고리즘의 효율이 낮을 수 있습니다.

댓글 환영합니다!