이친수 (2193)

(문제링크)

이친수의 κ·œμΉ™μ€ λ‹€μŒ 두 가지이닀.

  1. μ΄μΉœμˆ˜λŠ” 0으둜 μ‹œμž‘ν•˜μ§€ μ•ŠλŠ”λ‹€.
  2. μ΄μΉœμˆ˜μ—μ„œλŠ” 1이 두 번 μ—°μ†μœΌλ‘œ λ‚˜νƒ€λ‚˜μ§€ μ•ŠλŠ”λ‹€. 즉, 11을 λΆ€λΆ„ λ¬Έμžμ—΄λ‘œ 갖지 μ•ŠλŠ”λ‹€.

쒀더 μ‰½κ²Œ ν•΄μ„ν•˜λ©΄ λ‹€μŒκ³Ό κ°™λ‹€.

  1. N자리 이친수의 μ²«μ§Έμžλ¦¬λŠ” 무쑰건 1둜 μ‹œμž‘ν•œλ‹€.
  2. 00 λ‹€μŒμ—λŠ” 11μ΄λ‚˜ 00이 올 수 μžˆμ§€λ§Œ, 11λ‹€μŒμ—λŠ” 00만 올 수 μžˆλ‹€.

이 κ·œμΉ™μ„ ν† λŒ€λ‘œ 각 자리의 이친수 개수λ₯Ό ν‘œλ‘œ ν‘œν˜„ν•  수 μžˆλ‹€.
0 1 2 3 4 5
0 0 1 1 2 3
1 1 0 1 1 2
SUM 1 1 2 3 5
d[1][0] = 0;
d[1][1] = 1; // μ΄μΉœμˆ˜λŠ” 1둜만 μ‹œμž‘ν•  수 μžˆλ‹€.
d[2][0] = 1; // κ·ΈλŸ¬λ―€λ‘œ λ‘λ²ˆμ§Έ μžλ¦¬λŠ” 무쑰건 0만 κ°€λŠ₯ν•˜λ‹€.
d[2][1] = 0;
d[2][0] = 1; // μ„Έλ²ˆμ§Έ μžλ¦¬λŠ” 1, 0 λͺ¨λ‘ κ°€λŠ₯ν•˜λ‹€.
d[2][1] = 0;

μ΅œμ’…μ½”λ“œ

#include <stdio.h>

long long d[91][2];
int main(){
    int n,i;
    scanf("%d", &n);

    d[1][0] = 0;
    d[1][1] = 1;
    d[2][0] = 1;
    d[2][1] = 0;

    for(i=3;i<=n;i++){
        d[i][0] = d[i-1][0] + d[i-1][1];
        d[i][1] = d[i-1][0];
    }

    printf("%lld", d[n][0] + d[n][1]);

    return 0;
}

μ΅œμ’…μ½”λ“œ 2

#include <stdio.h>

long long d[91]={0,1,1};
int main(){
    int n,i;
    scanf("%d",&n);
    
    for(i=3;i<=n;i++){
        d[i]=d[i-2]+d[i-1];
    }
    
    printf("%lld",d[n]);
    return 0;
}

μ΅œμ’…μ½”λ“œ 3

#include <stdio.h>

int main(){
    long long x = 1, y = 1, curr = 0, tmp = 0;
    int n,i;
    scanf("%d",&n);
    
    if(n < 3){
        printf("1");
    }else{
        while(n--){
            curr = x + y;
            if(n>2){
                tmp = y;
                y = curr;
                x = tmp;
            }
        }
        printf("%lld",curr);
    }
    return 0;
}