[백준] 2193 : 이친수 JAVA 풀이

이번 문제도 상당히 어려웠다..

문제의 난이도 자체가 높다기보단 내 경험치가 부족한 탓인 것 같다.

 

이친수는 0으로 시작하지 않고 1이 두번 연속으로 나타나지 않아야 한다.

이는 N번째 자리 수가 0일 경우에는 그 이전에 1이 나오든 0이 나오든 상관이 없지만

1일 경우에는 반드시 0이어야 한다는 걸 의미한다.

 

그래서 N번째 자리수가 0인 이친수의 개수와 1인 이친수의 개수를 나눠서 세기 위해 2차원 배열을 사용했다.

이때 입력될 수 있는 N의 범위가 1부터 90까지인데 이는 int에 저장할 수 있는 크기를 넘어서기 때문에

long형으로 선언해줘야 한다.

long dp[][] = new long[N+1][2];

이제 dp[?][0]에는 끝자리가 0인 이친수의 개수를, dp[?][1]에는 1인 이친수의 개수를 저장할 것이다.

그러기 위해서 초기화시켜줘야 하는 값이 있다.

바로 N이 1일 때 즉, 한자리수 이진수의 이친수 개수이다.

한자리수 이진수는 0아니면 1인데 이친수는 0으로 시작할 수 없으니

dp[1][0] = 0;

dp[1][1] = 1; 이다.

 

그리고 두자리수부터는 반복문을 돌면서

N번째 자리수가 0일 때는 그 앞이 0이든 1이든 상관이 없으니 두 경우를 더하고

1일 때는 앞 숫자가 0인 경우만 가능하니 그 경우만 고려하도록 코드를 짜면 된다. 

 

import java.io.IOException;
import java.io.BufferedReader;
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[][] dp = new long[N+1][2];
        
        dp[1][0] = 0;
        dp[1][1] = 1;
        
        for(int i=2;i<=N;i++){
            for(int j=0;j<2;j++){
                if(j==0){
                    dp[i][j] = dp[i-1][0]+dp[i-1][1];
                } 
                else{
                    dp[i][j] = dp[i-1][0];
                } 
            }
        }
        long sum = 0;
        for(int i=0;i<2;i++) sum += dp[N][i];
        
        System.out.println(sum);
    }
}

---

이 문제를 푼 지 삼일이 됐는데, 완벽히 이해하지 못했던 것 같아서 다시 풀어봤다.

그랬더니 이번에 N=4일쯤부터 피보나치 수열과 같은 규칙이 적용된다는 걸 알게 돼서

피보나치 수열을 이용해서 풀어봤다.

(int로는 피보나치수열의 46번째항정도까지밖에 담지 못한다는 것도 알게 됐음!)

 

import java.io.*;
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[] dp = new long[N+1];
        
        dp[1] = 1;
        if(N>=2){
            dp[2] = 1;
        }
        for(int i=3;i<=N;i++){
            dp[i] = dp[i-1]+dp[i-2];
        }
        System.out.println(dp[N]);
    }
}