백준 9095번 - 1, 2, 3 더하기 (C#)

오늘은 백준 9095번 문제를 풀었다.
문제는 간단하게 말하면 정수 n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 문제다.

https://www.acmicpc.net/problem/9095

문제 설명

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 경우의 수를 구해야 한다.

예를 들어, n = 4라면 아래와 같이 7가지 경우가 있다.

1 + 1 + 1 + 1  
1 + 1 + 2  
1 + 2 + 1  
2 + 1 + 1  
2 + 2  
1 + 3  
3 + 1  
=> 총 7가지

접근 방법

처음에는 재귀로 접근해볼까도 했지만, 시간 초과가 쉽게 날 수 있기 때문에
DP(동적 계획법) 으로 해결하기로 했다.

핵심은 다음과 같은 점화식을 세우는 것이다.

dp[n] = dp[n-1] + dp[n-2] + dp[n-3]

• n을 만들기 위해서는 마지막에 1, 2, 3 중 어떤 수가 왔는지가 중요하다.

• 예를 들어, dp[4]는

  	dp[3]에서 +1 한 경우
  
  	dp[2]에서 +2 한 경우
  
  	dp[1]에서 +3 한 경우
  	로 나뉠 수 있다.

따라서 위의 점화식을 사용하면 된다.

초기값 설정

dp[1] = 1       // [1]
dp[2] = 2       // [1+1], [2]
dp[3] = 4       // [1+1+1], [1+2], [2+1], [3]

작성 코드

using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;

namespace backjoon
{
    internal class Program
    {

        static void Main()
        {

            int t = int.Parse(Console.ReadLine()); // 테스트 케이스 개수

            int[] dp = new int[12]; // n의 최대값이 11이므로 넉넉하게 12로 설정
            dp[1] = 1;
            dp[2] = 2;
            dp[3] = 4;

            // 미리 DP 배열 채워놓기
            for (int i = 4; i <= 11; i++)
            {
                dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
            }

            // 테스트 케이스 실행
            for (int i = 0; i < t; i++)
            {
                int n = int.Parse(Console.ReadLine());
                Console.WriteLine(dp[n]);
            }


        }

        
    }
}

느낀점

작은 문제를 풀어놓고 그걸 이용해서 큰 문제를 푸는 방식은 익숙해질수록 시간이 많이 절약된다.

앞으로는 문제를 볼 때 부분 문제로 쪼갤 수 있는가? 를 먼저 고민해봐야겠다.