[C++ / 9095] 1, 2, 3 더하기

문제

9095번: 1, 2, 3 더하기

---

문제 설명

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

단, 2가 주어진다면 방법의 수에 2도 포함이 된다. 그리고 4를 구현함에 있어서 1+1+2, 2+1+1 같은 경우는 다른 경우로 판단한다.

예를 들어,정수 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

---

풀이 방식

이 문제는 해당 문제와 비슷한 유형의 Dynamic Programming 문제이다.

이전 결과가 현재의 값을 구하는데 영향을 미친다는 것이다.

 

이 문제를 풀기 위해서 1부터 경우의 수를 하나씩 구해보자

1의 경우 (1개)
- 1

2의 경우 (2개)
- 1+1
- 2

3의 경우 (4개)
- 1+1+1
- 1+2
- 2+1
- 3

4의 경우 (7개)
- 1+1+1+1
- 2+1+1
- 1+2+1
- 1+1+2
- 2+2
- 3+1
- 1+3

5의 경우 (13개)
- 1+1+1+1+1
- 2+1+1+1
- 1+2+1+1
- 1+1+2+1
- 1+1+1+2
- 2+2+1
- 2+1+2
- 1+2+2
- 3+1+1
- 1+3+1
- 1+1+3
- 3+2
- 2+3

...

위에서 총 n이 주어졌을때, 만들수 있는 총 개수를 보면 1, 2, 4, 7, 13 ... 이런 식으로 증가하고 있는데 7은 1+2+4이고 13은 7+4+2 이다.

이를 검증해 보기 위해서는 계속 구해보면 될 것이다.

 

즉, n이 1, 2, 3인 경우에는 해당되지 않지만 4 부터는 어떠한 규칙을 띄고 있다.

이에 대한 점화식을 구해보면

dp(n) = dp(n-1) + dp(n-2)+ dp(n-3)

다음과 같이 나타낼 수 있다.

 

다음 식을 이용한 재귀 함수를 구현해 문제를 풀면 된다.

---

솔루션

#include <iostream>
#include <vector>

using namespace std;

int dp(int v)
{
  if (v == 1)
    return 1;
  else if (v == 2)
    return 2;
  else if (v == 3)
    return 4;
  else
    return dp(v - 1) + dp(v - 2) + dp(v - 3);
}

int main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  int n;

  cin >> n;
  vector<int> v(n);

  for (int i = 0; i < n; i++)
  {
    cin >> v[i];
    cout << dp(v[i]) << endl;
  }
}

---

여담

최근 DP와 관련된 문제를 풀어보면서 많이 익숙해진것 같다.

예전에는 알고리즘 잘 푸는 사람들이 신기했는데 하다 보니까 점화식 까지는 모르겠지만 음~ 이건 DP로 풀면 되겠구나 이런 감이 조금 생겼다.

 

차후 카카오 코딩테스트 같은 것을 풀수 있을 정도로 성장하면 좋겠다..ㅎㅎ