[재귀] 백준: 1, 2, 3 더하기

 

https://www.acmicpc.net/problem/9095

 

 

---

1. 문제 이해

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

 

1, 2, 3을 사용해서, 1, 2, 3의 합으로 n을 나타내는 방법의 수를 구하는 것.

 

 

---

 

2. 재정의 & 추상화

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

 

== 1, 2, 3을 사용하여 n을 나타내는 모든 경우의 수를 구하여라. == 완전 탐색 문제 == 재귀, 분할 정복등을 사용 

 

 

 

---

3. 설계

 

재귀적 접근 : 함수 내부에서 for 문으로 1, 2, 3을 돌면서 n - 1, n - 2, n - 3한 값을 다시 함수에 인자로 넣음. 기저 사례는 n이 0일 시와 n이 1일시. 이 경우, 경우의 수의 마지막에 도달했으니 1을 리턴.

 

 

 

 

 

---

4. 검증

n이 1, 2, 3일때 =>  조건을 만족. 

n이 최대 10이므로, 모든 경우의 수 = 3^10의 경우의 수는 충분히 1초안에 계산 가능.

 

---

 

5. 구현

 

 

#include <iostream>

using namespace std;

int recursion(int n)
{
  if (n == 1 || n == 0)
    return 1; // 기저 사례

  int count = 0;

  for (int i = 1; 4 > i; i++)
    if (n - i >= 0) // n < i가 되는 경우를 제외함.
      count += recursion(n - i);
  return count;
}

int main(void)
{
  int N, n;

  cin >> N;

  while (N--)
  {
    cin >> n;
    cout << recursion(n) << '\n';
  }

  return 0;
}

 

 

 

---

6. 회고 & 피드백

 

 

메모이제이션이나 분할 정복으로 풀 수 있을까? 메모이제이션은 좀 더 생각을 해 봐야겠고, 분할 정복의 경우, n == 2이나 n == 3인 경우의 수를 미리 지정해서 n < i 가 되는 경우의 수를 차단하면,

return recursion(n - 1) + recursion(n - 2) + recursion(n - 3);

을 통해 가능하지 싶다.