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

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

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 문제다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

 

---

문제 탐색하기

- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정

ex. 가능한 시간 복잡도, 알고리즘 선택

입출력 제한

• 1 ≤ N ≤ 10

 

N이 1부터 10까지의 정수이기 때문에 모든 N에 대해 직접 쓰면서 수를 세봐도 간단하게(?) 구할 수 있는 문제다.

1년 전엔 아래 코드를 제출해서 정답 처리가 됐다. 🙃 왜 제출했을까?

#include <iostream>
using namespace std;

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  
  int t,n;
  cin >> t;
  for (int i=0; i<t; i++) {
    cin >> n;
    switch(n) {
      case 1: cout << 1 << '\n'; break;
      case 2: cout << 2 << '\n'; break;
      case 3: cout << 4 << '\n'; break;
      case 4: cout << 7 << '\n'; break;
      case 5: cout << 13 << '\n'; break;
      case 6: cout << 24 << '\n'; break;
      case 7: cout << 44 << '\n'; break;
      case 8: cout << 81 << '\n'; break;
      case 9: cout << 149 << '\n'; break;
      case 10: cout << 274 << '\n'; break;
      default: break;
    }
  }
}

 

물론 직접 쓰다보면 아래와 같은 간단한 점화식을 찾을 수 있다. 우선 1, 2, 3의 합으로 나타내는 방법의 수를 저장할 배열을 만들어야 한다.

dp[i] = dp[i-3] + dp[i-2] + dp[i-1]

N이 4일 때 예시를 들어보면, 위에 적어둔 대로 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다.

N=1

• 1

N=2

• 1+1
• 2

N=3

• 1+1+1
• 1+2
• 2+1
• 3

N=4

• 1+1+1+1
• 1+1+2
• 1+2+1
• 2+1+1
• 2+2
• 1+3
• 3+1

이런 식으로 살펴보면 (N=3일 때의 모든 경우에 뒤에 1을 더한 값) + (N=2일 때의 모든 경우에 뒤에 2를 더한 값) + (N=3일 때의 모든 경우에 뒤에 3을 더한 값) = (N=4일 때의 모든 경우) 인 것을 알 수 있다. 점화식을 통해 배열 값을 미리 채워두고 테스트 케이스에 따라 값을 알맞게 출력하면 된다.

 

---

코드 설계하기

위의 [문제 탐색하기]에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡고, 문제 풀이를 본격적으로 하기 전 이 문제를 풀기 위한 로드맵을 그리는 과정!

- 어떤 순서로 코드를 작성해야 할지
- 어떤 함수들을 작성해야 할지

1. 테스트 케이스 T 입력받기
2. dp 배열 값 미리 구해 두기
   1. 점화식 → dp[i] = dp[i-3] + dp[i-2] + dp[i-1]
3. 테스트 케이스마다 N을 입력받아 dp[N] 출력하기

 

---

시도 회차 수정 사항 (Optional)

- '틀렸습니다'를 받았다면 왜 틀렸는지 고민해보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검
- 한 번에 맞히면 pass해도 됨!

pass

 

---

정답 코드

#include <iostream>
using namespace std;

int t,n,dp[12];

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

    cin >> t;

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

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