1904번: 01타일
지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이
www.acmicpc.net
우선 점화식을 세워 패턴을 파악하기 위해 발생할 수 있는 경우의 수를 세보았다
1 = 1
2 = 11 00
3 = 111 100 001
4 = 1111 1100 0011 1001 0000
5 = 11111 11100 11001 10011 00111 10000 00100 00001이슈 1
전전칸에서 2칸이 늘어나는 경우를 생각해보자
2칸이 늘어나는 경우
xx 00
xx 11
x0 01(이 경우 이전 마지막 숫자가 0으로 바뀜)
이 세가지 경우가 추가될 수 있다
따라서 재귀를 위한 점화식을 세워보면
dp[N] = dp[N-2] *3 - 1
이렇게 될 것으로 예상하고 위 식에 적용해봤는데
N이 6이상일 경우에는 전혀 다른 값이 나오는 것을 확인하고 다시 확인해보니 피보나치 배열을 따르는 것을 확인했다
dp[i] = dp[i-1]+dp[i-2]이슈 2
탑다운 방식으로 풀어보려고 했으나 입력이 100000처럼 높은 수가 주어지면
재귀는 느리고 메모리 사용량이 너무 높아지기 때문에 테스트가 실패했다
따라서 비교적 빠르고 메모리 사용량이 적은 바텀업 방식으로 다시 풀었다
결과 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
private static Integer[] dp;
private static int r = 15746;
private static int BottomUp(int N) {
for (int i = 3; i <= N; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
dp[i] %= r;
}
return dp[N];
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
dp = new Integer[1000001];
dp[0] = 0;
dp[1] = 1;
dp[2] = 2;
System.out.println(BottomUp(N));
}
}
