백준_9461 파도반 수열(자바) / DP

시간&메모리 제한

 

문제

 

입력&출력

 

문제풀이

package com.Back;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Back_9461 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int testCase = Integer.parseInt(br.readLine());
		long [] arr = new long[101];
		arr[0] = 0L;
		arr[1] = 1L;
		arr[2] = 1L;
		arr[3] = 1L;
		
		for (int i = 4; i < 101; i++) {
			arr[i] = arr[i-3]+arr[i-2];
		}
		
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < testCase; i++) {
			int tmp = Integer.parseInt(br.readLine());
			sb.append(arr[tmp]+"\n");
		}
		System.out.println(sb);
	}
}

 

※ 내 생각

이 문제는 DP를 활용하는 문제입니다.
먼저 첫번재, 두번째, 세번째는 모두 1의 길이의 삼각형이므로 미리 지정을 해줍니다.

4번째 부터 규칙을 가지고 있습니다.
각각의 값을 3개 이전 값 + 2개 이전 값을 더한 값이 됩니다.