성능 요약
메모리: 14200 KB, 시간: 128 ms
분류
다이나믹 프로그래밍
제출 일자
2024년 4월 2일 18:35:59
문제 설명
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 (2차원 배열 DP 풀이)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main{
static long[][] dp; //맨 뒷자리가 1 혹은 0인 2차원 배열
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
dp=new long[N+1][2];
dp[1][1]=1; dp[1][0]=0; //1,0
for(int i=2; i<=N; i++) {
dp[i][0]=dp[i-1][1]+dp[i-1][0];
dp[i][1]=dp[i-1][0];
}
System.out.println(dp[N][0]+dp[N][1]);
}
}코드 1 문제 풀이 방법
여기 1 (N=1인 경우) 부터 10000 (N=5인 경우)까지 있다고 가정해보면 각각의 경우의 수는 다음과 같다.
이때 우리가 주목해야 할 점은 맨 뒷자릿수가 0으로 끝나는 지, 1로 끝나는 지이다.
CASE 1: 1로 끝나는 경우.
각각 1로 끝나는 경우는 다음과 같다.
본문에서 나왔듯 11 처럼 1이 겹치는 상황은 나올 수 없기 때문에, 1 (N=1인 경우)에서 10 (N=2인 경우)로 가려면 무조건 뒤에 0을 붙여야 한다.
이 관점에서 그림을 통해 다시 설명하면!
각각 10 , 1010 , 10010은 무조건 N-1의 맨 뒷자릿수가 1인 경우를 따라가게 된다.
그렇다면 역으로도 맞지 않을까?
반대로, 맨 뒷자릿수가 1인 경우는 무조건 N-1의 맨 뒷자릿수가 0인 경우를 따라가게 된다.
우리는 이 부분을 이용해서 수식으로 써보면...
DP[N][1] = DP[N-1][0]; 이라고 쓸 수 있을 것이다.
CASE 2: 0으로 끝나는 경우.
반대로 0인 경우는 이렇다.
이번에도 똑같이 N=2인 가장 낮은 경우의 수부터 생각해보자.
맨 뒷자리가 0인 경우엔, 뒤에 0 또는 1 둘 다 붙일 수 있게 된다.
이는 곧 2개의 가지로 뻗어갈 수 있음을 의미한다.
이를 다시 역으로 하여금 10000 (N=5인 경우)부터 내려가는 방식으로 생각해본다면
조금 그림 자체가 외계인마냥 바뀐 느낌인데...
그림에서 보게 되면 맨 상위, 즉 N=5인 경우에서 맨 뒷자릿수가 0일 때, N=4인 경우로 내려가게 된다면 각각의 N=4일 때의 원소가 모두 포함되게 된다.
이는 곧 DP[N]의 맨 뒷자릿수가 0인 경우는 반드시 DP[N-1]의 맨 뒷자릿수가 0,1인 경우의 수를 가진다는 의미이다.
이를 수식으로 쓰면
DP[N][0] = DP[N-1][0] + DP[N-1][1];라고 쓸 수 있을 것이다!
그래서 최종 문제 풀이 코드의 핵심은
DP[N][1] = DP[N-1][0];
DP[N][0] = DP[N-1][1] + DP[N-1][0];라고 할 수 있을 것이다.
코드 2 (1차원 배열 DP 풀이)
[이친수 1차원 배열 DP 문제 코드 + 풀이 참고]
본 풀이는 인터넷 검색하다가 "이렇게도 풀 수 있구나" 하는 마음으로 가져왔다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
long [] answer = new long[N+1]; // 정수형 범위를 초과하는 것에 주의한다.
answer[0] = 0;
answer[1] = 1;
for( int i =2; i<=N; i++){
answer[i] = answer[i-1]+answer[i-2];
}
System.out.println(answer[N]);
}
}