[백준] 2193번 : 이친 자바(JAVA) 풀이

문제

---

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

---

문제 탐색하기

• N자리 이친수의 개수 구하기
• N = 1인 경우, 이친수 개수 1개 (1)
• N = 2인 경우, 이친수 개수 1개 (10)
• N = 3인 경우, 이친수 개수 2개 (100, 101)
• N = 4인 경우, 이친수 개수 3개 (1000, 1001, 1010)
• 위의 결과를 보면, N자리는 N-1의 마지막 끝자리에 따라 결정난다.

1. 뒷자리가 0으로 끝나는 경우
   • 뒤에 0, 1 붙이기
2. 뒷자리가 1로 끝나는 경우
   • 뒤에 0 붙이기

DP 설계하기

• dp[i][0] : 숫자 N을 만드는 경우의 수 중 끝자리가 0인 경우의 수
• dp[i][1] : 숫자 N을 만드는 경우의 수 중 끝자리가 1인 경우의 수

1. 초기값
   • dp[1][0] = 0
   • dp[1][1] = 1
2. i 자리의 끝자리가 0으로 끝나는 경우
   • dp[i][0] = dp[i-1][0] + dp[i-1][1]
3. i 자리의 끝자리가 1로 끝나는 경우
   • dp[i][1] += dp[i-1][0]

 

가능한 시간복잡도

입력 범위 ( 1 ≤ N ≤ 90)

N까지의 DP를 탐색하기 위 for 문 시간 복잡도 O(N)

---

코드 설계하기

1. 이친수 개수를 구할 N자리를 입력받는다.
2. DP 초기값을 설정한다.
3. DP 점화식을 세운다
   • 뒷자리가 0으로 끝나는 경우 : 뒤에 0, 1 붙이기
   • 뒷자리가 1로 끝나는 경우 : 뒤에 0 붙이기
4. 뒷자리가 0인 경우의 수와 1인 경우의 수를 더한다.

 

---

풀이 코드

※ dp 값을 담을 배열을 생성할 때, long 타입으로 하는 것을 명심하자 !

int 타입으로 선언하면 32비트 크기까지만 저장할 수 있기 때문에 오버플로우가 생길 수 있다. long 타입은 64비트 크기까지 저장 가능

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[N+1][2];
		
		// 1 자리일 때
		dp[1][0] = 0; // 뒷자리가 0으로 끝나는 이친수
		dp[1][1] = 1; // 뒷자리가 1로 끝나는 이친수

		for(int i=2;i<N+1;i++) {
			// 뒷자리가 0으로 끝나는 경우 0,1 붙이기
			dp[i][0] = dp[i-1][0] + dp[i-1][1];
			// 뒷자리가 1로 끝나는 경우 0 붙이기
			dp[i][1] += dp[i-1][0];			
		}
		
		System.out.println(dp[N][0] + dp[N][1]);
		
	}
}