📌 문제
0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다.
- 이친수는 0으로 시작하지 않는다.
- 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다.
예를 들면 1, 10, 100, 101, 1000, 1001 등이 이친수가 된다. 하지만 0010101이나 101101은 각각 1, 2번 규칙에 위배되므로 이친수가 아니다.
N(1 ≤ N ≤ 90)이 주어졌을 때, N자리 이친수의 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다.
출력
첫째 줄에 N자리 이친수의 개수를 출력한다.
예제 입력 1
3
예제 출력 1
2📌 풀이
import java.io.BufferedReader;
import java.io.InputStreamReader;
class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
//N(1 ≤ N ≤ 90) 정수가 90자리 넘어가면 int 로 불가 -> long
//dp (왜냐면 dp[1] dp[2]가 정해져있음
long[] dp = new long[N+1]; //n자리 이친 수의 총 개수
dp[0] = 0;
dp[1] = 1;
// dp[n] n자리 수 끝에 0이 오는 경우 + 1이 오는 경우를 더하면 된다.
// n 자리에 0과 1 두 가지만 올 수 있다.
// n 자리에 0이 들어 오면, 앞에 0과 1 둘 다 들어올 수 있다.
// n 자리에 1이 들어 오면, 앞에 0만 들어올 수 있다.
for(int i=2; i<=N; i++) {
dp[i] = dp[i-1] + dp[i-2];
}
System.out.println(dp[N]);
}
}📌 기록
DP 에 정말 약하구나 라는걸 알고 있음에도 불구하고 계속해서 알아가고 있는 요즘입니다. 그래도 문제를 보고 DP 라는 사실은 알 수 있었습니다.
시간 복잡도를 생각해볼까요? N은 최대 90까지 됩니다. 완전 탐색으로 탐색할 경우 2^90의 경우가 되기때문에 완전탐색으로 풀 수 없습니다. 그렇다면 완전탐색이 아닌 문제에서 제공해준 2가지의 조건을 사용해서 문제를 풀어봐야합니다.
일단, 문제 조건은 총 2개입니다.
- 첫째 자리는 0으로 시작하지 않는다
- 1이 두 번 연속으로 나타나지 않는다.
여기서 핵심 아이디어는 “맨 끝자리에 0을 넣을지 1을 넣을지 생각하기” 입니다.
N = 1 일 경우, “1” 한 가지만 존재합니다
N = 2 일 경우, “10” 한 가지만 존재합니다. 그리고 2 이상일 경우 반드시 앞에는 10으로 시작해야 합니다.
N = 3 일 경우, “10_” 으로 0 또는 1이 올 수 있기 때문에 경우의 수는 2 입니다.
N = 4 일 경우, 뒷 자리에 집중해봅시다.
맨 끝자리가 0일 때를 생각해보면, “ _ _ _ 0 “ 이고, 앞 자리에는 0 또는 1이 올 수 있습니다. 그러면 N=3을 구하는 경우와 같습니다.
맨 끝자리가 1일 때를 생각해보면, “ _ _ 1 “ 이고, 앞 자리에는 0만 올 수 있습니다. 따라서 “ _ 0 1 “ 이고, N=2일때와 같습니다.
한번 더 생각해봅시다
N = 5 일 경우, 뒷자리에 집중해봅시다.
맨 끝자리 0인 경우 → “ _ _ _ _ 0 “ → N = 4를 구하는 경우와 같음
맨 끝자리 1인 경우 → “ _ _ _ 0 1 “ → N = 3을 구하는 경우와 같음
이를 통해 아래와 같은 점화식을 세울 수 있습니다.
