백준 - 2193번 - 이친수

2193번

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	static Long[][] dp;

	static long recur(int N, int M) {
		if (dp[N][M] == null) {
			dp[N][0] = recur(N-1, 0) + recur(N-1, 1);
			dp[N][1] = recur(N-1, 0);
		}
		return dp[N][M];

	}

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(bf.readLine());

		dp = new Long[91][2];
		dp[1][0] = 0l;
		dp[1][1] = 1l;

		long result = recur(N, 0) + recur(N, 1);
		System.out.print(result);
	}
}

풀이

1. DP문제인거 인지

   • 첫째자리 수가 1이면 다음에 0만 올 수 있다.
   • 첫째자리 수가 0이면 다음에 0과 1이 온다.
   • 위 두가지로 메모라이징해서 바텀업 방식으로 풀 수 있다.

2. 점화식 구현

   • 2차원 배열을 통해서 0과 1의 갯수만 카운팅해줬다.

dp[N][0] = recur(N-1, 0) + recur(N-1, 1);
dp[N][1] = recur(N-1, 0);

3. long 범위 활용