https://www.acmicpc.net/problem/2193
문제
> 0과 1로만 이루어진 수를 이진수라 한다.
> 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다.
> 이친수는 다음의 성질을 만족한다.
1. 이친수는 0으로 시작하지 않는다.
2. 이친수에서는 1이 두 번 연속으로 나타나지 않는다.
즉, 11을 부분 문자열로 갖지 않는다.
> 예를 들면 1, 10, 100, 101, 1000, 1001 등이 이친수가 된다.
> 하지만 0010101이나 101101은 각각 1, 2번 규칙에 위배되므로 이친수가 아니다.
> N(1 ≤ N ≤ 90)이 주어졌을 때, N자리 이친수의 개수를 구하는 프로그램을 작성하시오.접근
dp를 사용하여 해결하며 dp값을 저장할 배열은 이차원 배열을 사용한다.
이친수의 길이를 dp의 행으로, 각 자리에 0과 1 둘 중 하나가 오므로 열은 2로 하여 dp(N)(2)형태의 배열을 선언한다.
뒷자리가 1인 이친수는 직전에 0이 나왔어야만 가능하고, 0인 이친수는 직전에 1이나왔던, 0이 나왔던 상관없다 따라서 dp(i)(1)은 i-1,0의 값을 가지고, dp(i)(0)은 i-1,0과 i-1,1의 값을 더한 값을 가진다.
문제해결
> 자리수 N을 입력받고 N자리 까지 가능하므로 dp를 N+1,2 크기로 만들어준다.
> 초기값으로 첫자리는 무조건 1이와야 하므로 1,0은 못와서 0을, 1,1은 1가지이므로 1을 주고 시작한다.
> 2부터는 앞서 구한 공식을 적용하여 N자리까지 구해준다.
> 원하는 N자리의 경우는 dp(N,0)과 dp(N,1)즉, 0으로 끝나는 경우와 1로 끝나는 경우를 모두 더해준 경우가 된다.코드
import java.io.*;
import java.util.*;
import java.lang.*;
public class Main {
//2193번 이친수
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
long[][] dp = new long[N+1][2];
dp[1][0] = 0;
dp[1][1] = 1;
for(int i = 2; i <= N; i++) {
dp[i][0] = dp[i-1][0] + dp[i-1][1];
dp[i][1] = dp[i-1][0];
}
System.out.print(dp[N][0] + dp[N][1]);
}
}
후기
int로 dp를 선언해서 틀렸다. ide상에서 N의 최대값인 90을 넣으니 쓰레기 값이 나왔다. long으로 바꾼뒤 90을넣으니 제대로 나왔다. 앞으로 최대 범위를 넣고 쓰레기가 나오는지 꼭 확인해보자
