[PS 백준 - 5.4] 2193번: 이친수

문제 정보

백준 2193번 - 바로가기

• 난이도: 실버 3
• 알고리즘: 다이나믹 프로그래밍

코멘트

• [Parameters]
  • n: 이진수의 길이
  • digit: 첫번째 자릿수
• [base case]
  • 이진수 길이가 1일 때 첫번째 자릿수가 1이면 0 리턴, 0이면 1 리턴
• [Logic]
  이친수는 첫번째 자릿수가 0일 경우 그 다음 자릿수가 0 또는 1 모두 가능하고, 1일 경우 그 다음 자릿수는 0만 가능하다. 메모이제이션을 할 때 이진수 길이와 자릿수가 0/1인 경우를 모두 저장해야 한다.

소스 코드

<탑다운 방식>

#include <iostream>
#include <cstdio>
#include <string>
#include <cmath>
#include <vector>
#include <set>
#include <list>
#include <stack>
#include <queue>
#include <map>
#include <algorithm>

using namespace std;

long long int dp[91][2]{ 0, };

// n: 길이, digit: 첫 자리수
long long int pinary(int n, int digit) {
	// base case
	if (n == 1 && digit == 1) return 0;
	if (n == 1 && digit == 0) return 1;

	// memoization
	if (dp[n][digit] != 0) return dp[n][digit];

	long long int result = pinary(n - 1, 0);

	if (digit == 0) { // 0 또는 1 나옴
		result = pinary(n - 1, 0) + pinary(n - 1, 1);
	}
	dp[n][digit] = result;

	return result;
}

int main() {
	std::ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int n;
	cin >> n;
	cout << pinary(n, 0);
}

<바텀업 방식> - by zzoni

#include <iostream>
#include <algorithm>
using namespace std;

long long int dp[100];

long long int f(int n) {
    if (n == 1 || n == 2) return 1;
    if (dp[n] != -1) return dp[n];
    return dp[n] = f(n - 1) + f(n - 2);
}

int main() {
    std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    fill(dp, dp + 100, -1);

    int n; cin >> n;
    cout << f(n);
    return 0;
}