[백준] 9461번: 파도반 수열 - JAVA

🔗 문제 링크

BOJ 9461번: 파도반 수열

9461번: 파도반 수열

 

📝 풀이 과정

 

처음 변의 길이가 1인 정삼각형을 기준으로 시계방향으로 정삼각형을 추가하는 수열이다.

 

 

한 변의 길이가 2일 때까지는 한 변에 붙는 경우와 두 변에 붙는 경우도 존재하지만, 한 변의 길이가 3 이상이 되면 두 변에 걸쳐 삼각형이 생기는 것을 알 수 있다.

 

 

 

 

N = 6일 때, 1번째와 5번째 삼각형의 두 변의 걸쳐 생성되었고,
N = 7일 때, 2번째와 6번째, N = 8일 때, 3번째와 7번째 삼각형의 변을 맞대고 생성되었다.

따라서, $P(N) = P(N-1) + P(N-5)$ 라는 규칙을 찾을 수 있다.

 

N < 6일 때는 불규칙한 수열이기 때문에 값을 미리 대입하고, 이후로는 반복문을 통해 값을 대입하였다.

 

💡 단, N이 일정 값 이상 커지게 되면 Integer.MAX_VALUE를 넘게 되므로 int가 아닌 long으로 배열을 선언해주어야 한다! 언제나 범위에 조심하자!

 

💻 코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        long[] memo = new long[101];

        memo[1] = memo[2] = memo[3] = 1;
        memo[4] = memo[5] = 2;
        for (int i = 6; i <= 100; i++)
            memo[i] = memo[i - 1] + memo[i - 5];

        for (int tc = 1; tc <= T; tc++)
            System.out.println(memo[sc.nextInt()]);

    }
}

 

📊 제출 결과