백준(BOJ) 9095번 1,2, 3 더하기

안녕하세요, 오늘은 백준 알고리즘 사이트의 문제 중 9095번 1, 2, 3 더하기 문제를 풀어보려합니다.

먼저 문제부터 보겠습니다!

어떤 정수 n이 주어졌을 때, 이 n을 1,2,3의 합으로 나타내는 방법의 수를 구하는 문제입니다.

어떻게 접근해야할까요? 저는 DP(Dynamic Programming)로 접근해보겠습니다.

이 문제는 테스트 케이스 1개 이상이고 sub problem으로 main problem을 해결할 수 있으므로 DP로 접근하는 것이 바람직해보입니다.

정수 n이 1일 경우,

숫자 1에서 정수 1을 만들 수 있는 경우의 수는 1가지,

숫자 2에서 정수 1을 만들 수 있는 경우의 수는 0가지,

숫자 3에서 정수 1을 만들 수 있는 경우의 수는 0가지,

총 1가지

정수 n이 2일 경우,

숫자 1에서 정수 2를 만들 수 있는 경우의 수는, 숫자 1에서 정수 1를 만들 수 있는 튜플의 수와 같음, 왜냐하면 숫자 1에서 정수 1를 만든 튜플에서 원소 1를 추가하면 되기 때문, 즉 1가지

숫자 2에서 정수 2를 만들 수 있는 경우의 수는 1가지,

숫자 3에서 정수 2를 만들 수 있는 경우의 수는 0가지,

총 2가지

정수 n이 3일 경우,

숫자 1에서 정수 3을 만들 수 있는 경우의 수는 숫자 1에서 만든 정수 1를 만든 튜플에서 원소 2를 추가하고, 숫자 1에서 정수 2를 만든 튜플에서 원소 1를 추가하면 정수 3을 만들 수 있음, 총 2가지

숫자 2에서 정수 3을 만들 수 있는 경우의 수는 숫자 2에서 정수 2를 만든 튜플에서 원소 1를 추가하면 되기 때문에 1가지

숫자 3에서 정수 3을 만들 수 있는 경우의 수는 1가지

총 4가지

정수 n이 4일 경우,

숫자 1에서 정수 4를 만들 수 있는 경우의 수는 숫자 1에서 정수 1를 만든 튜플에서 원소 3을 추가하고, 숫자 1에서  정수 2를 만든 튜플에서 원소 2를 추가하고, 숫자 1에서 정수 3을 만든 튜플에서 원소 1를 추가하면 정수 4를 만들 수 있음, 즉 4가지

숫자 2에서 정수 4를 만들 수 있는 경우의 수는 숫자 2에서 정수 2를 만든 튜플에서 원소 2를 추가하고, 숫자 2에서 정수 3을 만든 튜플에서 원소 1를 추가하면 되므로 2가지

숫자 3에서 정수 4를 만들 수 있는 경우의 수는 숫자 3에서 정수 3을 만든 튜플에서 원소 1를 추가하면 되므로 1가지

총 7가지 

글로 쭉 나열하니까 이해가 잘 안되시죠??

테이블로 표현해보겠습니다.

이런 식으로 쭉 나열하면, 우리가 구하고 싶은 답을 얻을 수 있습니다.

코드로 옮겨보겠습니다.

 
#include <iostream>
#include <vector>
#include <algorithm>

int map[4][12];
void initialize();

int main() 
{
	int T, n; 
	std::cin >> T;
	initialize();
	
	while (T--) 
	{
		std::cin >> n;
		std::cout << map[1][n] + map[2][n] + map[3][n] << std::endl;
	}
	return 0;
}

void initialize() 
{
	map[1][1] = 1;
	map[1][2] = 1;
	map[1][3] = 2;
	map[2][2] = 1;
	map[2][3] = 1;
	map[3][3] = 1;
	for (int idx = 4; idx <= 11; idx++) 
	{
		map[1][idx] = map[1][idx - 1] + map[1][idx - 2] + map[1][idx - 3];
		map[2][idx] = map[2][idx - 1] + map[2][idx - 2] + map[2][idx - 3];
		map[3][idx] = map[3][idx - 1] + map[3][idx - 2] + map[3][idx - 3];
	}
}

코드를 설명하자면, initialize()함수는 사전에 미리 문제에서 나올 수 있는 모든 답을 구하도록 하였습니다.

테스트 케이스(문제)가 1개가 아니라 여러 개가 들어오기 때문에, 미리 모든 케이스의 답을 구해놓고 각 케이스의 답만 출력해주면 시간이 훨씬 절약되기 때문입니다.

위에서 설명한 로직을 그대로 initalize()함수에 옮겨놓았습니다.

감사합니다.