문제

BOJ 2193, 이친수

핵심

• 입력의 크기가 $90$이라 구현에 초점을 맞춘다.
• 이친수란 이진수 중 특별한 성질을 갖는 수이다. 이친수는 0으로 시작하지 않고 1이 두 번 연속으로 나타나지 않는 특징을 가진다. N자리 이친수의 개수를 구해야 한다.
• 이전에 1로 끝난 수는 반드시 뒤에 0이 붙어야 하고, 이전에 0으로 끝난 것은 뒤에 0과 1을 붙일 수 있다는 것을 활용해 다음과 같이 선언할 수 있다.
• dp[i]: i자리 이친수의 개수. 초깃값들을 생각해 보면
  • dp[1] = 1;
    • 1개 (1)
  • dp[2] = 1;
    • 1개 (10)
  • dp[3]
    • 2개 (101, 100)
  • dp[4]
    • 3개 (1010, 1001, 1000)
  • dp[5]
    • 5개 (10100, 10101, 10010, 10001, 10000)
• dp[i] = dp[i - 2] + dp[i - 1];로 점화식을 완성할 수 있다.
• 다른 방식으로 접근할 수도 있다. dp[i][k]: i자리 수 중 k로 끝나는 이친수의 개수. k는 0 또는 1.

dp[i][0] = dp[i - 1][0] + dp[i - 1][1];
dp[i][1] = dp[i - 1][0];

개선

코드

시간복잡도

• $O(N)$

C++

#include <iostream>
using namespace std;

long long dp[94];
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin >> n;
	dp[1] = 1;
	dp[2] = 1;
	for (int i = 3; i <= 90; ++i)
		dp[i] = dp[i - 2] + dp[i - 1];
	cout << dp[n];
}

Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] dp = new long[94];
        dp[1] = 1;
        dp[2] = 1;
        for (int i = 3; i <= 90; ++i)
            dp[i] = dp[i - 2] + dp[i - 1];
        System.out.println(dp[n]);
        sc.close();
    }