[백준] 2193번 - 이친수 [Java]

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

 

[백준] 2193번 - 이친수 [Java]

---

1.  아이디어

 

N자리 이친수는 N-1자리 이친수 뒤에 0을 하나 더 붙이거나 N-1자리 이친수 중 0으로 끝나는 이친수 뒤에 1을 붙여서 만들 수 있다.

---

2. 문제풀이

 

N이 최대 90까지라서 int형 오버플로우가 발생하는 점만 주의하면 된다. 추가로 규칙성을 통해 피보나치 수열을 이루는 점을 알 수 있어서 이를 활용한 1차원 dp 배열로도 해결할 수 있었다.

---

3. 코드

 

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[1 + N][2];
        dp[1][1] = 1;

        for (int i = 2; i <= N; i++) {
            dp[i][0] = dp[i - 1][0] + dp[i - 1][1];
            dp[i][1] = dp[i - 1][0];
        }

        System.out.println(dp[N][0] + dp[N][1]);
    }
}

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[1 + N];
        dp[1] = 1;

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

        System.out.println(dp[N]);
    }
}

---

4. 후기

 

- 2차원 dp

- 1차원 dp