[TIL] DP 연습 – 삼각 마을의 집 크기 문제 풀이

문제

삼각 마을에는 1번부터 N번까지의 집이 있다.
각 집의 크기는 규칙을 따르는데,
1~3번 집은 크기가 2, 4번 집은 3, 5번 집은 4이다.

6번 집부터는 다음 규칙이 적용된다.

H[n] = H[n-1] + H[n-3]

즉, 현재 집의 크기는 이전 집 크기 + 3번째 전 집 크기이다.

규칙 분석

초기값:

H[1] = 2  
H[2] = 2  
H[3] = 2  
H[4] = 3  
H[5] = 4

점화식 적용:

H[6] = H[5] + H[3] = 4 + 2 = 6  
H[7] = H[6] + H[4] = 6 + 3 = 9  
H[8] = H[7] + H[5] = 9 + 4 = 13  

9461번 파도반 수열처럼,
몇 개의 초기값을 미리 설정해두고 점화식으로 나머지를 구하는 방식이다.

작성한코드

using System;

namespace backjoon
{
    internal class Program
    {
        static void Main()
        {
            int t = int.Parse(Console.ReadLine());
            long[] dp = new long[101]; // 최대 N이 100

            // 초기값
            dp[1] = 2;
            dp[2] = 2;
            dp[3] = 2;
            dp[4] = 3;
            dp[5] = 4;

            // 점화식 적용
            for (int i = 6; i <= 100; i++)
            {
                dp[i] = dp[i - 1] + dp[i - 3];
            }

            // 출력
            for (int i = 0; i < t; i++)
            {
                int n = int.Parse(Console.ReadLine());
                Console.WriteLine(dp[n]);
            }
        }
    }
}

배운 점

9461번처럼 DP 문제는 규칙을 찾는 것이 가장 중요하다.

초기값을 올바르게 설정하면 점화식으로 쉽게 풀 수 있다.

N이 커질 수 있으니 long 타입을 써서 오버플로우를 방지해야 한다.

반복문 범위는<= 100으로 설정해 최대값까지 미리 계산해두는 습관이 좋다.