[백준, 자바] 2193번 - 이친수

문제 링크
https://www.acmicpc.net/problem/16194

최종 코드(정답)

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());
        long[] dp = new long[91];
        
        dp[1] = 1;
        dp[2] = 1;
        dp[3] = 2;
        for(int k = 4; k <= N; k++) {
            dp[k] = dp[k-1] + dp[k-2];
        }
        System.out.println(dp[N]);
    }
}

풀이
피보나치 수열이랑 풀이가 똑같다.

/**
 * 1 연속 금지, 0으로 시작 금지
 *
 * N == 1일때
 * 1, //1
 *
 * N == 2일때
 * 1, 10,  //2
 *
 * N == 3일때
 * 1, 10, 100, 101, //4
 *
 * N == 4일때,
 * 1, 10, 100, 101, 1000, 1001, 1010,  //7
 *
 * N == 5일때,
 * 1, 10, 100, 101, 1000, 1001, 1010, 10100, 10101, 10000, 10001, 10010, //12
 *
 * N == 6일때,
 * 1, 10, 100, 101, 1000, 1001, 1010, 10100, 10101, 10000, 10001, 10010, 100100, 100101, 100000, 100001, 100010, 101000, 101001, 101010, //20
 *
 *
 * 잘못 생각했다. 전체 개수 비교가 아니라 N개의 이친수만 구하는 것이었다.
 * 3자리수인 이친수만 구하는 것.
 *
 * dp[1] = 1
 * dp[2] = 1
 * dp[3] = 2
 * dp[4] = 3
 * dp[5] = 5
 * dp[6] = 8
 *
 */

처음에 1~N자리의 이친수를 모두 구하는 줄 착각했다가 다시 풀었다. 궁리를 해보니 결국 피보나치였다.

다만 int가 아니라 long을 써야 한다는 점에서 또 틀렸다.

N이 90일 때 값이 2,880,067,194가 나오는데, 이는 int형으로 처리할 수 없는 범위이기에 문제가 생기는 것.

dp[90] = 2,880,067,194는 int로 안되니 long을 쓰라는 것이다.

참고로 int는 2^31 - 1은 2,147,483,647까지 커버가 가능하다.