[코딩테스트 C++] 이친수

후이재·2020년 10월 18일
0

오늘의 문제

이친수

문제 접근

  • 배열을 개수만큼 만들긴했지만, 변수 두개만 있으면 풀 수 있는 문제다.
  • 이친수를 만드는 규칙을 생각하면 쉽게 생각할 수 있다.
  • 0으로 끝나는 경우들은 0을 붙일수도, 1을 붙일수도 있으므로 0, 1로 만들어지는 개수에 합한다.
  • 1로 끝나는 경우들은 0을 붙여야하므로 0으로 만들어지는 개수에 합한다.

나의 풀이

#include <iostream>
#include <vector>
using namespace std;
int n;
const int MAX = 90;
long long pinary[MAX][2] = {0, };

// 이친수
long long solution(){
    // 1로 시작, 1 두번연속 없음 N자리 이친수 개수
    pinary[0][1] = 1;
    for(int i=1;i<n;i++){
        pinary[i][0] = pinary[i-1][0] + pinary[i-1][1];
        pinary[i][1] = pinary[i-1][0];
    }
    return pinary[n-1][0] + pinary[n-1][1];
}

다른 답안

#include<stdio.h>
long long a[91]={0,1},N;
int main(){
	scanf("%d",&N);
	for(int i=2;i<=N;i++)a[i]=a[i-1]+a[i-2];
	printf("%lld",a[N]);
}

배울 점

  • 내가 푼 방법을 한줄로 만들수도 있다.
profile
공부를 위한 벨로그

0개의 댓글