[코딩테스트 C++] 2 x n 타일링 2

후이재·2020년 11월 6일
0

오늘의 문제

2 x n 타일링2

접근 방식

  • 전에 풀었던 2xn 타일링의 응용문제
  • 간단하게 2 전의 값에 2를 곱해주면 된다. 경우가 2배 늘어나므로!
  • 2 전의 값 *2와 1 전의 값을 더해주면 끝

나의 풀이

#include<iostream>
using namespace std;
int n;
const int DIV = 10007;

int solution(){
    if(n == 1)
        return 1;
    int dp[2];
    dp[0] = 1;
    dp[1] = 3;
    for(int i=2;i<n;i++){
        int temp = (dp[0]*2 +dp[1])%DIV;
        dp[0] = dp[1];
        dp[1] = temp;
    }
    return dp[1];
}

다른 풀이

#include <stdio.h>

int main(void) {
 
    int D [1001] = {};
    int N;
    D[1] = 1;
    D[2] = 3;
 
    scanf("%d", &N);
 
    for (int i = 3; i <= N; i++)  {
        D[i] =  (D[i-1] + 2*D[i-2]) % 10007;
    }
 
    printf("%d\n", D[N] % 10007);
    return 0;
}

배울 점

  • 워낙 답이 하나로 나오는 문제이기 때문에 똑같다~!
profile
공부를 위한 벨로그

0개의 댓글