9095. 1, 2, 3 더하기

이 글은 Obsidian에서 마이그레이션되었으며, 그 과정에서 AI의 도움을 받았습니다. 오류나 누락된 내용이 있다면 댓글로 알려주세요!

문제

9095번: 1, 2, 3 더하기

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

풀이

아이디어

방법의 수를 구하는 것이므로 일단 나열해 보았다. 중요한 것은 숫자들의 순서를 고려한다는 점이다. (1 + 2와 2 + 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
  • 1 + 1 + 2
  • 1 + 2 + 1
  • 2 + 1 + 1
  • 1 + 3
  • 3 + 1
  • 2 + 2
• 5를 나타내는 방법 => 13개
  • 1 + 1 + 1 + 1 + 1
  • 1 + 1 + 1 + 2
  • 1 + 1 + 2 + 1
  • 1 + 2 + 1 + 1
  • 2 + 1 + 1 + 1
  • 1 + 1 + 3
  • 1 + 3 + 1
  • 3 + 1 + 1
  • 1 + 2 + 2
  • 2 + 1 + 2
  • 2 + 2 + 1
  • 2 + 3
  • 3 + 2

적어보니 1, 2, 3의 합으로 n을 나타내는 방법의 수인 dp[n]은 dp[n-3] + dp[n-2] + dp[n-1]이라는 점화식을 따른다는 것을 알 수 있었다.

점화식을 활용해야 하므로 DP를 이용해서 미리 모든 방법의 수를 구한 다음에, 테스트케이스에 따라서 답을 출력해 주었다.

보통은 재귀로 DP를 구현하는 편이 더 깔끔한데 이 문제는 간단해서 그냥 반복문을 이용해서 구현해 주었다.

코드

/*
2022-1-8
9095_1, 2, 3 더하기
https://www.acmicpc.net/problem/9095
*/

#include <iostream>

using namespace std;

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

	int dp[12];
	int T, n;

	//초깃값 설정
	dp[0] = 0;
	dp[1] = 1;
	dp[2] = 2;
	dp[3] = 4;

	// dp 배열 채우기
	// 점화식: dp[n] = dp[n-3] + np[n-2] + dp[n-1]
	for(int i = 4; i < 12; i++)
		dp[i] = dp[i-3] + dp[i-2] + dp[i-1];

	// 문제 해결
	cin >> T;
	for(int i = 0; i < T; i++){
		cin >> n;
		cout << dp[n] << '\n';
	}

    return (0);
}