[BOJ] #9095 - 1, 2, 3 더하기

👻 1, 2, 3 더하기

👉🏻 문제 보러가기 👈🏻

---

🌱 문제

정수 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의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

• 시간 제한 : 1초 (추가 시간 없음)
• 메모리 제한 : 512 MB

---

🌱 입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.

---

🌱 출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.

---

🌱 예제

---

🪐 입출력 1

• 입력

  3
  4
  7
  10
  

• 출력

  7
  44
  274
  

---

👻 풀이

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

int T, n;
int cache[15];

int AddCount(int num)
{
    if (num < 0)
        return 0;
    if (num == 0)
        return 1;

    int& ret = cache[num];
    if (ret != -1)
        return ret;

    return ret = AddCount(num - 1) + AddCount(num - 2) + AddCount(num - 3);
}

int main()
{
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    // 1, 2, 3 더하기
    ::memset(cache, -1, sizeof(cache));

    cin >> T;
    while (T--)
    {
        cin >> n;
        cout << AddCount(n) << '\n';
    }

    return 0;
}

• 시간 : 0 ms
• 메모리 : 2020 KB

---

👻 글을 마치며

DP 문제의 원리를 알면 쉽게 풀 수 있는 문제이다. 하지만 재귀 함수와 알고리즘에 대한 개념 이해가 완벽히 되지 않는다면 생각하는 데 시간이 꽤 걸릴 것 같다. 다양한 문제를 통해 사고 방식을 유연하게 하는 것이 가장 중요한 것 같다.

---

소스코드 보러가기