문제 정보
- 백준 실버 3
- DP
- 문제 링크
풀이
1과 00을 이용해 길이 N의 수열을 만드는 경우의 수를 구하는 문제다.
길이 N인 수열의 마지막을 기준으로 나누면 다음과 같다.
- 마지막이
1로 끝나는 경우: 앞의n - 1길이의 수열의 경우의 수 - 마지막이
00으로 끝나는 경우: 앞의n - 2길이의 수열의 경우의 수
따라서 점화식은 dp[n] = dp[n - 1] + dp[n - 2]로, 피보나치 수열과 동일한 구조다.
초기값은 prev2(dp[1]) = 1(1), prev1(dp[2]) = 2(00, 11)다.
코드
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
final int MOD = 15746;
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
int answer;
if (n == 1) {
answer = 1;
} else if (n == 2) {
answer = 2;
} else {
int prev1 = 2;
int prev2 = 1;
int cur = 0;
for (int i = 3; i <= n; i++) {
cur = (prev1 + prev2) % MOD;
prev2 = prev1;
prev1 = cur;
}
answer = cur;
}
bw.write(answer + "\n");
bw.flush();
bw.close();
}
}