[JAVA] 백준 2193_이친수

 

[문제링크]

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

 

 

📌 문제 탐색하기

이친수... 특성을 보면 이전 자리의 숫자에 따라서 다음 자리의 숫자가 결정되기 때문에 문제를 재귀적으로 해결하는 방식을 사용해야하는 문제인거 같다. 

 

> 이친수란 ? ( 정리 예정 )

 

📌 가능한 시간복잡도 

for문이 n번 반복되기 때문에 가능한 시간복잡도는 O(N)입니다.

 

📌 코드 설계하기

DP를 활용해서 해결하는 문제라고 생각함.

 

이친수에 대해서 공부하는데 시간이 조금 오래걸렸음...

 

1.입력받기 

: N값 입력받고 

2. DP사용할거니까 dp[i]으로 i자리 이친수 개수 저장해서 점화식 적용하기

3. 출력하기

: dp[n]출력해서 n 자리 이친수 개수 구하기

 

📌 정답 코드

import java.util.Scanner;

public class Main {

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

        int n = scanner.nextInt();
        scanner.close();

        long[] dp = new long[n + 1];

        dp[1] = 1;
        if (n > 1) {
            dp[2] = 1;
        }

        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        System.out.println(dp[n]);
    }
}