[백준] 2193번 이친수 문제 다이나믹 프로그래밍으로 풀기
1. 문제
1) 링크
2) 문제
0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다.
- 이친수는 0으로 시작하지 않는다.
- 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다.
예를 들면 1, 10, 100, 101, 1000, 1001 등이 이친수가 된다. 하지만 0010101이나 101101은 각각 1, 2번 규칙에 위배되므로 이친수가 아니다.
N(1 ≤ N ≤ 90)이 주어졌을 때, N자리 이친수의 개수를 구하는 프로그램을 작성하시오.
3) 입력
첫째 줄에 N이 주어진다.
4) 출력
첫째 줄에 N자리 이친수의 개수를 출력한다.
더 자세한 문제의 조건을 확인해보기 위해서는 위의 링크에 클릭해서 들어가보자
2. 풀이
이 문제는 만약 우리가 ans[n]을 n자리 이친수의 개수라고 정의했다는 가정 하에서 시작된다.
만약 ans[n] 중에서 마지막 자리가 0으로 끝났다면 그 윗자리는 0이나 1이나 무엇이 오든지 관계가 없다. 따라서 그냥 ans[n-1] 과 값이 동일하다고 할 수 있다. n-1자리 이친수에다가 0을 추가한 것이기 때문이다. 하지만 만약에 마지막 자리가 1로 끝났다면 그 윗자리 수는 1이 올 수 없다. 그러므로 ans[n-2]와 값이 같게 된다. n-2자리 이친수에다 그 다음 자리는 무조건 0, 마지막 자리는 무조건 1이 오기 때문이다.
따라서 우리는 이를 ans[n]= ans[n-1] + ans[n-2] 라고 정의할 수 있다. 그러므로 n이 1일때부터 시작하여서 문제에서 주어진 값에 해당하는 값을 찾을 때까지 for문을 사용하여 구해주면 된다.
여기서 vector의 값으로 <int> 를 사용해주면 숫자가 초과되서 '틀렸습니다'가 나온다. 그러므로 <long long>을 써주어야 한다. 이 주의사항 빼고는 위의 점화식을 알면 쉽게 코드화시킬 수 있다.
이친수는 가장 작은 값이 최소 1자리는 되어야 하므로 ans[1]이 시작점이다. ans[1]의 경우 1밖에 될 수 없기 때문에 ans[1]의 값은 1이고, ans[2]의 값은 10 밖에 될 수 없기 때문에 ans[2] 또한 1의 값을 가지게 된다.
3. 코드
이 두 값을 가지고 for문을 돌리면서 Bottom-Up방식으로 문제를 해결해주면 된다.
#include <iostream>
#include <vector>
using namespace std;
int main(){
int n;
cin>>n;
vector<long long> ans(n+1);
ans[1]=1; //무조건 한 자리는 있어야 하므로 1부터 시작
ans[2]=1; // 10밖에 가능하지 않음.
for(int i=3; i<=n; i++){
ans[i]=ans[i-1]+ans[i-2];
}
cout<<ans[n]<<"\n";
return 0;
}
이 문제는 다만 0과 1만을 사용한다고 했기 때문에 이렇게 간단하게 구현할 수 있었던 것이다. 만약 0, 1, 2를 사용한다고 했으면 이렇게 1차원 배열을 사용해서 구할 수 없다. Binary의 상황이기 때문에 간단하게 구현할 수 있었던 문제이다