백준 9461번 파도반 수열 (C#)

문제

삼각형 변의 길이가 일정한 삼각형이 붙어 있는 도형이 있다.
1번째부터 N번째 삼각형의 한 변의 길이를 구하는 문제다.

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

문제에서 주어진 초기값:

1, 1, 1, 2, 2, ...

N이 커질수록 규칙이 반복되는데, 이를 찾아내야 한다.

규칙 찾기

그림과 예시를 살펴보면, 6번째 변부터는 다음 규칙이 적용된다.

P[n] = P[n-1] + P[n-5]

• n번째 변의 길이는 이전 변(P[n-1])과 5개 전 변(P[n-5])의 합

• 이 규칙을 이용하면 N이 100까지 커져도 쉽게 구할 수 있다.

점화식 예시

초기값:

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

점화식 적용:

P[6] = P[5] + P[1] = 2 + 1 = 3  
P[7] = P[6] + P[2] = 3 + 1 = 4  
P[8] = P[7] + P[3] = 4 + 1 = 5  
P[9] = P[8] + P[4] = 5 + 2 = 7  
P[10] = P[9] + P[5] = 7 + 2 = 9  

작성한코드

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());
            long[] dp = new long[101]; // 최대 N이 100이라서 101칸

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

            // 점화식으로 채우기
            for (int i = 6; i <= 100; i++)
            {
                dp[i] = dp[i - 1] + dp[i - 5];
            }

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

배운 점

• 규칙을 찾는 것이 DP 문제의 핵심

• N이 클 때는 미리 배열에 값을 채워두고 O(1)로 꺼내 쓰는 방식이 효율적

• 값이 커질 수 있으므로 long 타입을 사용해야 한다