[백준] 2193번 : 이친수 (Java)

think2wice·2020년 8월 6일
0

코딩 잘하지 못해요😂 풀이나 코드에 문제가 있다면 언제든 댓글로 알려주세요! 혹은 훨씬 좋은 풀이가 있다면 저도 알려주세요 :)
github 링크 👈

문제

문제 설명

0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다.

이친수는 0으로 시작하지 않는다.
이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다.
예를 들면 1, 10, 100, 101, 1000, 1001 등이 이친수가 된다. 하지만 0010101이나 101101은 각각 1, 2번 규칙에 위배되므로 이친수가 아니다.

N(1 ≤ N ≤ 90)이 주어졌을 때, N자리 이친수의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다.

출력

첫째 줄에 N자리 이친수의 개수를 출력한다.

Solution

해결법

이 문제는 동적 프로그래밍 방식으로 해결해야하는 문제입니다. 동적 프로그래밍 문제는 "(1)문제 속에서 점화식을 도출 (2)재귀 혹은 반복을 통해 코드 작성"의 과정으로 풀어나가면 됩니다. 재귀 혹은 반복으로 답을 도출해 나가는 중에 사용해야하는 기법이 있는데요. 바로 메모이제이션(Memoization) 입니다. 메모이제이션은 쉽게 말해 메모하는 것 입니다. 동적 프로그래밍은 작은 규모의 문제를 해결하며 큰 규모의 문제를 쉽게 푸는 방식입니다. 작은 규모의 문제를 해결하며 그 값을 메모해 놓고 큰 규모의 문제를 풀 때 메모해둔 값을 이용합니다. 메모되어 있는 값을 이용한다면 더욱 빠른 성능을 낼 수 있겠죠:) 메모해둘 메모장으로는 배열을 이용합니다. 자 그럼 문제로 돌아가 봅시다. 이 문제의 점화식을 세우기 위해 저는 n이 1인 경우부터 차례대로 자리수를 늘려가며 값을 확인해 보았습니다. "자리수 : n"을 f(n)이라 표시하겠습니다.

  • f(1)=1
  • f(2)=1
  • f(3)=2
  • f(4)=3
  • f(5)=5
  • f(6)=8
  • f(7)=13

위의 값을 살펴보면 일정한 규칙이 보입니다. f(1)과 f(2) 이후의 수를 살펴보면 f(n)의 값이 이전 두 값의 합이라는 식을 도출해낼 수 있습니다. 즉, 점화식을 정의하면 f(n) = f(n-1) + f(n-2) 라고 할 수 있습니다. 이 점화식을 이용해서 전 재귀방식으로 문제를 해결하였습니다. 문제 해결😎 이라고 하고 싶었으나 이상하게도 "틀렸습니다!"라는 문구를 받았습니다. 무엇이 문제인지 많이 고민했습니다. 점화식도 확인해보고 다른 점화식도 생각해보았으나 큰 문제는 없어 보였습니다. 문제를 다시 읽어보니 답을 구할 때 사용하는 재귀함수와 메모이제이션으로 활용할 배열을 long타입으로 선언해야 한다는 사실을 발견했습니다. N의 범위가 90까지 주어졌기 때문에 int의 범위를 넘어가 버립니다. 범위 체크를 했어야 했는데 꼼꼼하지 못했던 것 같습니다. 무튼 , 문제 해결😎

Code

import java.util.*;
/**
 * Top-bottom
 * 수행시간 : 112ms
 */
public class Main {
    public static long [] checked;

    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        checked = new long [n+1];

        System.out.println(dp(n));

    }

    public static long dp(int n){

        if(n==1) return 1;
        else if(n==2) return 1;
        else if(checked[n]!=0) return checked[n];
        else{
            return checked[n] = dp(n-1) + dp(n-2);
        }
    }
}



reference

profile
두번 생각해보는 꼼쭈의 코딩 세상⌨️

0개의 댓글