Algorithm/BOJ
BOJ 9461 파도반 수열
wow
2021. 3. 31. 22:05
9461번: 파도반 수열
오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의
www.acmicpc.net
문제 분석
- dp문제이다.
- f(n) = f(n-2) + f(n-3)
- 배열의 타입은 long으로 선언해준다.
문제 풀이
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
private static long[] map;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
for (int i = 0; i < T; i++) {
int N = Integer.parseInt(br.readLine());
map = new long[101];
map[0] = 0;
map[1] = 1;
map[2] = 1;
for (int j = 3; j <= N; j++) {
map[j] = map[j - 2] + map[j - 3];
}
System.out.println(map[N]);
}
}// main
}// class-end