BOJ 2193 : 이친수 -C++

7637 단어 DPbojDP

이친수

  • 해당 문제는 결과적으로 피보나치 점화식으로 풀리긴 한다.
    하지만, 이것은 해당 문제의 본질을 파악한 것은 아님
  • key point! (본질을 파악한 풀이)
    1) 해당 자리수에서 끝이 0으로 끝나는 요소는 0과 1이 붙을 수 있다
    ex) 100 -> 101 / 100
    2) 해당 자리수에서 끝이 1로 끝나는 요소는 0만 붙을 수 있다
    ex) 101 -> 100

코드

#include <string>
#include <vector>
#include <iostream>
using namespace std;
// d[i][1] = i 자리수 일 때 끝이 1인 개수
// d[i][0] = i 자리수 일 때 끝이 0인 개수
long long d[92][2]; 
int N;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N;
    d[1][1] = 1; 
    d[2][0] = 1; 
    d[3][0] = 1; d[3][1] = 1;
    for(int i=4;i<=N;i++)
    {
        d[i][0] = d[i-1][0] + d[i-1][1];
        d[i][1] = d[i-1][0];
    }
    cout << d[N][0] + d[N][1];
    return 0;
}
  • 테이블 정의
    D[i][0] = i 자리수 2진수 중 0으로 끝나는 요소의 개수
    D[i][1] = i 자리수 2진수 중 1으로 끝나는 요소의 개수
  • 점화식
    D[i][0] = D[i-1][0] + D[i-1][1]
    D[i][1] = D[i-1][0]
  • 점화식 이해하기
    ex)
    i가 4일 경우 1000 / 1010 / 1001 이렇게 3가지 가 나오는데,
    끝이 0인 요소는 뒤에 0과 1을 추가할 수 있으며,
    끝이 1인 요소는 뒤에 0만 추가해야한다.
    즉, 1000 -> 10000 / 10001
         1010 -> 10100 / 10101
         1001 -> 10010 이 된다!
    결과적으로,
    D[5][0]D[4][0] + D[4][1]
    (끝이 0이 되는 것 = 전 자리수의 0요소 개수 + 전 자리수 1의 개수)
    D[5][1]D[4][0]
    (끝이 1이 되는 것 = 전 자리수의 0요소 개수)

좋은 웹페이지 즐겨찾기