ray

ray

매일의 HIGHLIGHT를 찾아서 ✨

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

Posted on Mar 4, 2021 #동적프로그래밍(DP)   #Algorithm  

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

🙌 입출력

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

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

🙋‍♂️ 예제 입출력

3
4
7
10

7
44
274

🚀 코드

#include <iostream>
#include <cstdlib>
#include <vector>
using namespace std;

vector<int> dpTable(12);

void dp(int n) {
	dpTable[0] = 0;
	dpTable[1] = 1;
	dpTable[2] = 2;
	dpTable[3] = 4;

	for (int i = 4; i <= n; i++) {
		dpTable[i] = dpTable[i - 1] + dpTable[i - 2] + dpTable[i - 3];
	}

	cout << dpTable[n] << '\n';
	return;
}


int main() {
	ios::ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int t = 0;
	int n = 0;

	cin >> t;
	for (int i = 0; i < t; i++) {
		cin >> n;
		dp(n);
	}
	return 0;
}

🌠 메모

딱 보자마자 다이나믹 프로그래밍을 써서 풀고 싶었다. 역시나 점화식을 생각하는 것이 가장 큰 문제였다.

살짝 감이 왔는데 앞에 구한 숫자에 1, 2, 3을 더하면 되는건가? 근데 그러면 순서는 어떡하지? 생각에 빠져 점화식은 한번에 찾지 못하였다.

4의 경우,

  • 1 + ‘3’
  • 1 + 1 + ‘2’, 2 + 2’
  • 1 + 1 + 1 + ‘1’, 1 + 2 + ‘1’, 2 + 1 + ‘1’ 로 이루어져 있는데, 앞에 하이라이팅 되지 않은 부분은 각각 dpTable[1], dpTable[2], dpTable[3]에 저장된 부분이다. 즉 n의 경우, n-1, n-2, n-3의 경우에 각각 1을 더하는 방법, 2를 더하는 방법, 3을 더하는 방법으로 이루어져 있을 것이다.

따라서 점화식은 dpTable[i] = dpTable[i - 1] + dpTable[i - 2] + dpTable[i - 3]으로 간단하게 세울 수 있다.

이 문제의 경우는 n이 최대 11까지라서 꼭 다이나믹 프로그래밍으로 풀지 않아도 되는데, [백준] 15988 1, 2, 3 더하기 3 문제의 경우에는 오버플로우도 있고 꼭 dp로 풀어야만 하는 문제이다.



# 카테고리