백준 2193 이친수

DP를 활용하여 문제를 해결할 수 있다.

규칙을 찾으면 쉽게 해결할 수 있다.
첫번째, 두번째 자리는 무조건 1과 0으로 고정

• 테이블 정의
  - d[i][0]는 10 고정 이후 0으로 시작하는 i자리 이친수 개수
  - d[i][1]는 10 고정 이후 1로 시작하는 i자리 이친수 개수
• 점화식 찾기
  - d[i][0] = d[i-1][0]+d[i-1][1];
  - d[i][1] = d[i-1][0];
• 초기값 정의
  d[1][0] = 0; d[1][1] = 1;
  d[2][0] = 1; d[2][1] = 0;
  d[3][0] = 1; d[3][1] = 1;
  

주의할 점

처음에 답을 제출할 때는 자료형을 int로 해서 오답을 받았다.
아무리 해도 맞는 코드인데 왜 틀렸을까를 생각하다가 자료형을 long long으로 고치니 바로 해결되었다.

코드를 구현하기 전, 자료형을 잘 생각해서 테이블을 설정하자
맞는 코드라도 원인을 못 찾아 헤맬 수 있다.

뒤늦게 피보나치 수열인 것을 알았지만, 굳이 모르더라도 점화식 자체는 매우 간단했다.

코드

#include <bits/stdc++.h>
using namespace std;
#define ll long long

int d[95][2];

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n; cin >> n;
    d[1][0] = 0; d[1][1] = 1;
    d[2][0] = 1; d[2][1] = 0;
    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];
    // 1
    // 10
    // 10 0 10 1

    // 10 0 0 0 1 / 1 0

    // 10 0 00 0 10 0 01
    // 10 1 00 1 01

    // 10 0 000 0 001 0 010 0 100 0 101
    // 10 1 000 1 010 1 001
}