[C++] 백준(BOJ) - 15989 : 1, 2, 3 더하기 4

04 Apr 2024 in Develop on C++, Algorithm

인프런에 있는 큰돌님의 강의 10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트를 듣고 정리한 필기입니다.

• 문제
• 입력
• 출력
• 알고리즘
• 풀이
• 코드
• 평가

문제

BOJ - 15989 : 1, 2, 3 더하기 4(링크)

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 4가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다.

• 1+1+1+1
• 2+1+1 (1+1+2, 1+2+1)
• 2+2
• 1+3 (3+1)

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

입력

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

출력

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

알고리즘

1. DP

풀이

• 주어진 n이 10000 이하의 수이므로 구해야 하는 상태 값은 경우의 수 뿐
• 경우의 수는 1로 만드는 경우의 수, 2로 만드는 경우의 수, 3으로 만드는 경우의 수가 독립적
  • 각 경우의 수를 더해 나가며 dp 1차원 배열에 저장

코드

// BOJ - 15989 : 1, 2, 3 더하기 4
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll t, n, dp[10001];

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

	cin >> t;
	dp[0] = 1;

	// 1로 만드는 경우의 수 위에 2로 만드는 경우의 수, 3으로 만드는 경우의 수를 더해 나가기
	for (int i = 1; i <= 3; i++)
	{
		for (int j = 0; j <= 10000; j++)
		{
			if (j - i >= 0) dp[j] += dp[j - i];
		}
	}

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

	return 0;
}

평가

• 각 케이스로 만드는 경우의 수는 독립적 => dp 배열에 중첩해 나가며 정답 도출 가능
• DP를 잘하는 팁
  • 문제를 잘 정의
  • 부분 문제들 사이의 관계를 파악