[백준/BOJ] 9461번 : 파도반 수열 (Java)

문제요약

나선 모양으로 놓여지는 N번째 정삼각형 변의 길이를 구하시오.

 

풀이

P(1) = P(2) = P(3) = 1

P(4) = P(5) = 2

P(6)부터 P(N) = P(N-5) + P(N-1)

 

다른 사람의 풀이를 보니, P(4)부터 P(N) = P(N-3) + P(N-2)로 풀이 할 수 있었다.

 

코드

시간 복잡도 O(N)

import java.util.Scanner;

public class BOJ_9461 {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int t = scan.nextInt();
		
		for (int i=0; i<t; i++) {
			int n = scan.nextInt();
			System.out.println(getSideLength(n));
		}
		
		scan.close();
	}
	
	public static long getSideLength(int n) {
		long[] sideLengths = new long[101];
		sideLengths[1] = sideLengths[2] = sideLengths[3] = 1;
		sideLengths[4] = sideLengths[5] = 2;
		
		for (int i=6; i<=n; i++) {
			sideLengths[i] = sideLengths[i-5] + sideLengths[i-1];
		}
		
		return sideLengths[n];
	}

}