[BAEKJOON]2193 이친수

문제 요약

• 알고리즘 분류: dp
• 난이도: Silver3
• 문제내용:
  • 이친수는 0으로 시작하지 않는다.
  • 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다.
• 사이트: https://www.acmicpc.net/problem/2193

2193번: 이친수

문제풀이

 이번 문제에는 모든 경우의 수를 구해서 풀기가 힘들다. 10^N개 탐색 하면 시간 초과로 나올 것이다. 그래서 이번 문제는 DP로 풀어야 통과 되는 문제이다. DP랑 관련된것은 자세한 내용은 아래의 글로 확인 해보면된다.

https://jih3508.tistory.com/89

[알고리즘 이론] 동적계획법(Dynamic Programming, DP)

 

문제 접근방법

 dp는 구현보다 아이디어를 요구하는 문제로서 생각만 한다면 코드 구현은 간단한다. 데이터가 최대 1000개이고 초당 2천만번 연산이 가능하다고 가정할때 O(N )으로 풀어야 통과가 될것이다.  일단 아래의 그림으로 N = 7까지 경우의 수를 확인 해보자

 여기서 확인 해봐야 할 경우는 뒤에 0과 1 올 경우만 확인 해보면 된다. 0은 앞에 어떤 수가 오던 간에 다 가능한데 1은 붙일수 없기 때문에 01로 와야 한다. 그래서 아래 그림 처럼 구조가 나온다.

위 2가지 경우수를 합하면된다. 즉 DP[N] = DP[N - 1] + DP[N + 2]라는 결과가 나온다. 

 

Code

Python

N = int(input())
dp = [0] * 91
dp[1], dp[2] = 1, 1
for i in range(3, N + 1):
    dp[i] = dp[i - 1] + dp[i - 2]

print(dp[N])

Java

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

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