[Java] 2193. 이친수

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

문제 접근 과정

 

• 이친수는 자리수를 기준으로 끝자리(0 또는 1)에 따라 앞의 숫자 조합이 결정됩니다.
• 끝자리가 1인 경우:
  • 그 앞에는 반드시 0만 올 수 있습니다.
• 끝자리가 0인 경우:
  • 그 앞에는 0과 1 모두 올 수 있습니다.

 

 

점화식

DP 배열 정의:

• dp[length][0]: 길이가 length이고, 끝자리가 0인 이친수의 개수
• dp[length][1]: 길이가 length이고, 끝자리가 1인 이친수의 개수

점화식:

1. 끝자리가 0인 경우:
   • 앞에 올 수 있는 숫자는 0과 1 모두 가능하므로: dp[length][0]=dp[length−1][0]+dp[length−1][1]
2. 끝자리가 1인 경우:
   • 앞에 올 수 있는 숫자는 0만 가능하므로: dp[length][1]=dp[length−1][0]

초기 조건:

• 길이가 1인 이친수는 끝자리가 1인 경우밖에 없으므로: dp[1][0]=0, dp[1][1]=1

 

코드

import java.io.*;
import java.util.Arrays;

public class Main {
	private static long[][] dp;

	private static long cal(int length, int lastDigit) {
		if (length == 1) {
			return lastDigit == 1 ? 1 : 0;
		}

		if (dp[length][lastDigit] != -1) {
			return dp[length][lastDigit];
		}

		long result = 0;

		if (lastDigit == 0) {
			result = cal(length - 1, 0) + cal(length - 1, 1);
		} else if (lastDigit == 1) {
			result = cal(length - 1, 0);
		}

		dp[length][lastDigit] = result;

		return result;
	}

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

		dp = new long[length + 1][2];

		for (long[] row : dp) {
			Arrays.fill(row, -1);
		}

		long total = cal(length, 0) + cal(length, 1);

		System.out.print(total);
	}
}