[알고리즘/DP/JAVA] 백준 2193 - 이친수

[알고리즘/DP/JAVA] 백준 2193 - 이친수

문제 : 백준 2193 - 이친수

문제 : https://www.acmicpc.net/problem/2193

2193번: 이친수

 

사용언어 : JAVA

 

시간제한 : 2초

메모리 제한 : 128 MB

 

문제 설명

 이진수 숫자 중 아래 성질을 만족하는 수들을 이친수라고 한다.

 

   이친수 조건

1. 이친수는 0으로 시작하지 않는다.
2. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다.

 숫자 n이 주어질 때 n자리의 이친수 갯수를 구해야하는 문제이다.

 

입력

첫째 줄에 N이 주어진다. (1 <= n <= 90)

예제 입력

3

 

출력

 N 자리 이진수의 이친수 갯수를 출력한다.

예제 출력

2

 

사용된 알고리즘

사용된 알고리즘 : DP(동적 계획법, Dynamic Programming)

 DP란 특정 문제를 풀기 위해 여러 하위 문제들로 나눈 뒤, 하위 문제들의 해결법을 저장하고 그를 사용하는 문제 해결 방식이다. 

 

아래는 N에 따른 이친수의 수이다.

• N = 1, 1
• N = 2, 1
• N = 3, 2
• N = 4. 3
• N = 5, 5
• N = 6, 8
• N = 7, 13 ...

이 수를 들여다 볼 경우 아래와 같은 수식을 도출 할 수 있다.

 

$F_{n} = 1$ (n == 1 or n == 2)

$F_{n} = F_{n-1} + F_{n-2}$ (n > 2)

 

 

문제 특성상 n의 범위가 한정되어 있다. 이럴 때 크기가 90인 배열을 활용하여 문제를 풀이할 수 있다. 크기가 90인 정수 배열을 선언하고 크기가 1, 2 일 때 이친수 수가 1임을 초기화 해주기위해 0번, 1번 배열에 1을 할당한다.

 

그 후 반복문을 사용하여 [i]번 째 배열을 [i - 2]번 배열의 수 + [i - 1]번 배열의  수로 할당한다.

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());
        //배열 선언
        int[] arr = new int[90];
        
        //f(1) = 1, f(2) = 1
        //n > 2; f(n) = f(n-2) + f(n - 1)
        
        //크기 1, 2 일 때 초기화
        arr[0] = 1;
        arr[1] = 1;
        //일종의 DP, 이전 크기의 이친수 수 이용하여 결과 도출
        for (int i = 2; i < 90; i++) {
            arr[i] = arr[i - 2] + arr[i - 1];
        }
        System.out.println(arr[n-1]);
    }

}

 

 

 

이 수식은 바로 피보나치 수열과 거의 동일한 형태이다. 즉 이 문제와 유사하다.

 

문제의 주요 오답

 위 코드를 제출하면 정답일까? 아쉽게도 아니다.

 

 

 그렇다면 어디에서 오답이 발생하는 걸까?

 

 n = 90일 경우의 결과값을 출력해보자. 아래와 같이 -1581614984라는 음수값이 출력됨을 확인할 수 있다.

 

 이는 n=90일 경우의 결과값이 정수형 자료형 int의 표현 가능 범위인 - 2147483648 ~ 2147483648를 벗어나 오버플로우가 발생하였기 때문에 값이 왜곡되어 출력되게 된다. 이를 해결하기 위해 int가 아닌 long 배열로 선언한다면 결과값이 long 표현 가능 범위에 들어가기 때문에 정상적으로 출력되는 것을 확인할 수 있다.

 

문제의 해답

해답 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) throws IOException {
        // TODO Auto-generated method stub
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        //배열 선언
        long[] arr = new long[90];
        
        //f(1) = 1, f(2) = 1
        //n > 2; f(n) = f(n-2) + f(n - 1)
        
        //크기 1, 2 일 때 초기화
        arr[0] = 1;
        arr[1] = 1;
        //일종의 DP, 이전 크기의 이친수 수 이용하여 결과 도출
        for (int i = 2; i < 90; i++) {
            arr[i] = arr[i - 2] + arr[i - 1];
        }
        System.out.println(arr[n-1]);
    }

}

 

참고

1. 위키백과 - 동적 계획법, 

https://ko.wikipedia.org/wiki/%EB%8F%99%EC%A0%81_%EA%B3%84%ED%9A%8D%EB%B2%95

동적 계획법 - 위키백과, 우리 모두의 백과사전

2. 피보나치 수열 풀이, https://potato-idiot.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EC%9E%AC%EA%B7%80%ED%98%B8%EC%B6%9CPython-%EB%B0%B1%EC%A4%80-2747-%ED%94%BC%EB%B3%B4%EB%82%98%EC%B9%98-%EC%88%98?category=1266397 

[알고리즘/재귀호출/Python] 백준 2747 - 피보나치 수