[JAVA] 백준 9461번

9461번 - 파도반 수열

 

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

public class Main {

	static long[] dp = new long[101]; // int로 선언시 n = 79일때 결과값이 21억을 넘어감

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

		dp[0] = 0;
		dp[1] = dp[2] = 1;

		for (int i = 0; i < T; i++) {

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

			if (dp[N] == 0) { // 이미구한 dp값이 존재하지 않는 경우
				for (int j = 3; j <= N; j++) {
					dp[j] = dp[j - 3] + dp[j - 2];
				}
			}
			bw.write(String.valueOf(dp[N]));
			bw.newLine();

		}

		bw.flush();
		bw.close();
	}

}

 

정답을 맞춘 풀이방법

1. DP[N] = DP[N-3] + DP[N-2]의 점화식을 가진 DP문제로 Bottom-Up방식으로 해결함

2. 입력이 한번이 아닌 여러번 주어질 수 있기 때문에 미리 static 변수로 선언함

3. int 배열로 dp 선언시 n = 79 정도 일때 int 자료형의 값을 벗어나기 때문에 long으로 선언

4. 결과 계산 후 출력함