백준 2193번 <이친수>

백준 알고리즘 2193번

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

2193번: 이친수

---

2193번

이친수는 이진수 중 아래의 조건을 만족하는 수이다.

1. 0으로 시작하지 않는다.
2. 1이 두 번 연속 나타나지 않는다.

n자리 이친수의 개수를 구하여라.

 

입력으로 첫 줄에 n이 주어진다.

 

출력으로 n자리 이친수의 개수를 출력하면 된다.

---

문제 해결

다이나믹 프로그래밍으로 해결할 수 있다.

 

먼저 dp 배열을 2개 만들었다. 

zero[i] : i자릿수 이친수 중 0으로 끝나는 개수

one[i] : i자릿수 이친수 중 1으로 끝나는 개수

 

1이 두 번 연속 나타나지 않기 때문에 one[i] = zero[i-1]이다.

0은 두 번 연속 나타날 수 있기 때문에 zero[i] = zero[i-1] + one[i-1]

 

zero[0]과 zero[1]은 먼저 채운다.  마찬가지로 one[0]과 one[1]은 먼저 채운다.

또한 n=1일 수도 있기 때문에 조건문으로 처리한다.

---

코드

package bj2193;

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[] zero = new long[n+1];
		long[] one = new long[n+1];
		
		if(n == 0) {
			System.out.println(1);
		}else {
			zero[0] = 0;
			zero[1] = 0;
			one[0] = 0;
			one[1] = 1;
			
			for(int i = 2; i < n+1; i++) {
				zero[i] = zero[i-1] + one[i-1];
				one[i] = zero[i-1];
			}
			
			System.out.println(zero[n] + one[n]);

		}
		
	}

}

---

결과

---

이친수의 개수가 int 자료형을 넘어갈 수 있기 때문에 long 자료형을 사용해야 한다.