[PS 백준 - 5.4] 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;
}
Author And Source
이 문제에 관하여([PS 백준 - 5.4] 2193번: 이친수), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@yjwon20/PSboj5-4저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)