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

문제

 

 

접근 방식

각 변의 길이가 1인 정삼각형으로 시작해 n번째 정삼각형의 한 변의 길이를 구해야 한다.

 

 

삼각형을 위와 같이 나선 모양으로 회전하면서 추가할 때

 

 

위와 같이 한 변의 길이가 이전 변의 길이보다 커질 때 새로운 삼각형을 추가해주고

이 때 새로운 정삼각형의 새로운 한 변의 길이는 dp[i] = dp[i - 1] + dp[i - 5]라는 것을 알 수 있다.

 

dp[i-5]를 계산하기 위해 dp 테이블의 dp[1] ~ dp[5]까지를

각각 순서대로 1, 1, 1, 2, 2로 초기화 해준 후에

dp[6] ~ dp[n]까지 구한 공식대로 계산해주면 된다.

 

계산하다 보면 인트형의 범위를 벗어나니 long 타입으로 저장해줘야 한다.

 

풀이

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		int t = Integer.parseInt(br.readLine());

		long[] dp = new long[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];
		}

		while (t-- > 0) {
			int n = Integer.parseInt(br.readLine());

			sb.append(dp[n]).append("\n");
		}

		System.out.println(sb);
	}
}