DP - 2193 (이친수)

2193번: 이친수 (acmicpc.net)

2193번: 이친수

 

1부터 시작해서 1이 두번 연속으로 나타나지 않는 이친수를 찾는 문제였습니다. 

 

• 1
• 10
• 100,101
• 1010,1001,1000
• 10101,10010,10000,10001,10000

 

이런식의 패턴을 볼 수 있습니다. 가지수는 1 , 1 , 2 , 3 , 5, 8 ,13의 패턴을 나타내고 이 패턴은

피보나치 수열임을 알 수 있었습니다. 간단하게 피보나치 수열만 구현한다면, 해결할 수 있었습니다. 

이번에는 Bottom-up 방식을 통해서 구현해보았습니다. 

import java.util.Scanner;

public class Main {
    static long number[] = new long[91];

    public static long cal(int num){


        number[0] = 1;
        number[1] = 1;

        for(int i=2; i<num; i++){
            number[i] = number[i-1] + number[i-2];
        }

        return number[num-1];
    }



    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
            System.out.println(cal(n));
    }
}

 

 

부족했던 점

 

처음에 풀이를 할때 패턴을 구하는데 실수를 하여서 다른 방식으로 풀었습니다. 백준에서 채점결과 피보나치를 사용하는 쪽이 더 빨랐습니다.

 

피보나치를 사용한 경우 

 

아래의 코드를 사용한 경우

import java.util.Scanner;

public class Main {
    static long number[][] = new long[1001][10];

    public static long cal(int level , int num){

        long sum = 0;

            number[1][1] = 1;
            number[2][0] = 1;

        for(int i=3; i<=level; i++){
            for(int j = 0; j<num; j++){
                    if(j == 0) { number[i][j] += number[i-1][0] + number[i-1][1]; }
                    else if(j == 1){ number[i][j] += number[i-1][0];}
            }
        }

        for(int k =0; k<num; k++){
            sum += number[level][k];
        }
        return sum;
    }



    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
            System.out.println(cal(n,2));
    }
}