9461번 파도반 수열

문제 링크 : www.acmicpc.net/problem/9461

9461번: 파도반 수열

---

---

<풀이 요점>

 - 미리 주어진 예시를 보면 i번째 삼각형의 변의 길이는 i-1번째 삼각형과 i-5번째 삼각형의 변의 길이의 합과 같다. 

 

 

 

<알고리즘>

  1) ArrayList에 0~4번째까지의 값을 미리 입력함

  2) 5번째 값부터는 i-1번째와 i-5번째의 값을 더해서 추가로 입력

  3) 이를 N번째까지 반복하여 결과값 찾아 출력

 

 

 

<주의할 점>

  - list에 들어가는 객체값이 어느 순간 int의 범위를 벗어날 수 있으므로 가능한 큰 데이터형을 주어야함.

 

 

 

메모리 : 11740KB   시간 : 96ms

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

public class Main {
	public static void main(String[] args) {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		String s = "";
		try {s=bf.readLine();}catch(IOException e) {}
		int T = Integer.parseInt(s);
		
		while(T!=0) {
			try {s=bf.readLine();}catch(IOException e) {}
			int N = Integer.parseInt(s);
			ArrayList<Long> list = new <Long> ArrayList();
			list.add(0, (long)0);
			list.add(1, (long)1);
			list.add(2, (long)1);
			list.add(3, (long)1);
			list.add(4, (long)2);
			for(int i =5;i<=N;i++) {
				list.add(i, (long)(list.get(i-1)+list.get(i-5)));
			}
			System.out.println(list.get(N));
			--T;
		}
	}
}