문제 출처

1. 문제설명

  • 각 테스트 케이스마다 정수 n이 주어진다.
    • 1<=n<=10,000
  • 정수 n이 주어졌을 때, n을 1,2,3의 합으로 나타내는 방법의 수를 구하라



2. 알고리즘 설계

  • 4까지의 경우는 다음과 같다.
  • n=1
    • 1
  • n=2
    • 1+1
    • 2
  • n=3
    • 1+1+1
    • 1+2
    • 3
  • n=4
    • 1+1+1+1
    • 2+2
    • 3+1
  • n을 1, 2, 3의 합으로 만드는 방법
    • 1 : n-1을 1로 만드는 경우
    • 2 : n-2를 1 또는 2로 만드는 경우
      • 2를 뺏으니 1+1, 2가 들어올 수 있는 것
    • 3 : n-3을 1, 2 또는 3으로 만드는 경우



3. 로직

  • 1, 2, 3을 만드는 경우에 대한 배열 선언
    • 편의상 [4]
    • 최대 10,000이므로 편의상 [10001]
  • n이 1,2,3일 때의 개수를 미리 저장해두고,
    • 4부터 10000까지 DP



4. 전체 코드

#include <iostream>
using namespace std;

int memo[10001][4] = { 0, };

void DP()
{
	memo[1][1] = 1;
	memo[2][1] = 1, memo[2][2] = 1;
	memo[3][1] = 1, memo[3][2] = 1, memo[3][3] = 1;

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

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	DP();

	int tc; cin >> tc;
	while (tc--) {
		int n; cin >> n;
		cout << memo[n][1] + memo[n][2] + memo[n][3] << '\n';
	}
}


5. 소감

  • 2차원 DP
    • 아직 몇 문제 풀어보지 않아서
    • 2차원으로 푸는 게 너무 낯설다
  • 점화식을 생각해내면 금방 풀 수 있는 문제