[백준 - C#] 9461번 파도반 수열

문제링크

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

9461번: 파도반 수열

 

문제

오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다.
첫 삼각형은 정삼각형으로 변의 길이는 1이다.
그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다.
나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다.

파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다.
P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다.

N이 주어졌을 때, P(N)을 구하는 프로그램을 작성하시오.

조건

시간제한 : 1초
메모리 제한 : 128 MB

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다.
각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. (1 ≤ N ≤ 100)

출력

각 테스트 케이스마다 P(N)을 출력한다.

 

문제정리

1. 가장 긴 변의 길이를 k라 하고, 그 변에 길이가 k인 정삼각형을 추가한다.
2. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9 이다.
3. N이 주어졌을 때 P(N)을 구하는 프로그램을 만들어야합니다.

이번 문제의 경우 P(N)을 구하는 문제인데 숫자가 나열 되어 있을 때 점화식?을 찾고 풀이를 하는 문제였습니다.

솔직히 삼각형이 어떻게 나선으로 도는지는 잘 이해가 안되지만 숫자를 나열하고 보니 하나의 규칙을 찾을 수 있었습니다.

1 1 1 2 2 3 4 5 7 9 12 16 21 28
숫자의 순서를 나열 해보면 1번째랑 2번째를 더했을 때 4번째가 나오게 되고 2번 째랑 3번째를 더하게되면 5번째가 나오게 되는것을 확인할 수 있습니다. 

위에서 말한 방식대로 나열하면 아래와 같이 나오게 되는데,
1 + 1 = 2
1 + 2 = 3
2 + 2 = 4
2 + 3 = 5
3 + 4 = 7
4 + 5 = 9
5 + 7 = 12
7 + 9 = 16
9 + 12 = 21
12 + 16 = 28

dp[i] = dp[i-3] + dp[i-2]의 식을 찾을 수 있습니다.

주의할점으로는 N에 100을 넣어보니 int 자릿수를 넘는 것 같아 long으로 변수를 바꿔주었으며,

N이 1, 2 인 경우도 있어 배열에 크기를 더 늘려주었습니다. ( OutOfRange 에러가 납니다. )

 

더 자세한 내용은 아래 코드를 보면 확인해보면 쉽게 알 수 있습니다.

 

C# 코드

static void Main(string[] args)
{
    //  https://bokhead.tistory.com/
    // 9461
    StreamWriter writer = new StreamWriter(Console.OpenStandardOutput());
    StreamReader reader = new StreamReader(Console.OpenStandardInput());
 
    // 테스트 케이스 개수 T
    int T = int.Parse(reader.ReadLine());
    for (int i = 0; i < T; i++)
    {
        int N = int.Parse(reader.ReadLine());
 
        // N값이 1, 2 인경우 때문에 처음에 3을 그냥 더했습니다. ( N의 크기가 100으로 작기 때문에 )
        long[] dp = new long[3 + N + 1];
 
        dp[1] = 1;
        dp[2] = 1;
        dp[3] = 1;
 
        for (int j = 4; j <= N; j++)
        {
            // 점화식
            dp[j] = dp[j - 2] + dp[j - 3];
        }
 
        writer.WriteLine(dp[N]);
    }
 
    writer.Close();
    reader.Close();
}

읽어주셔서 감사합니다 오늘도 즐거운 하루 되세요.