https://www.acmicpc.net/problem/9461
풀이
이 문제는 깊게 생각을 안 했다.
문제에 있는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9 수열을 보자마자
arr[i] = arr[i-2] + arr[i-3] 의 점화식을 떠올렸다.
이를 dp배열을 생성하여 그대로 구현
(주의)
dp배열을 int형으로 선언 시 계산값이 오버플로우가 발생할 수 있음
long타입으로 선언할 것.
package dp;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class BOJ_9461_파도반수열 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
long[] dp = new long[101];
dp[1] = 1L;
dp[2] = 1L;
dp[3] = 1L;
for(int i=4; i<=100; i++) {
dp[i] = dp[i-2]+dp[i-3];
}
int TC = Integer.parseInt(br.readLine());
StringBuilder sb = new StringBuilder();
for(int tc=1; tc<=TC; tc++) {
int now = Integer.parseInt(br.readLine());
sb.append(dp[now]).append("\n");
}
System.out.println(sb.toString());
}
}
'코딩테스트 > BOJ' 카테고리의 다른 글
[백준/BOJ] 댄스 파티 (Java/자바) (1) | 2023.11.28 |
---|---|
[백준/BOJ] 소문난 칠공주 (Java/자바) (0) | 2023.11.28 |
[백준/BOJ] 1068번 트리 (Java/자바) - dfs (0) | 2023.11.22 |
[백준/BOJ] 2012번 등수 매기기 (JAVA/자바) - 그리디(Greedy) (0) | 2023.11.07 |
[백준/BOJ] 1543번 문서검색(JAVA/자바) (0) | 2023.11.07 |