[PCCP] Lv2: 2xn 타일링(12900) 해설

문제

- 문제 링크: 2xn 타일링

 

해설

- 자료구조: 

- 시간복잡도: 

 

(풀이과정)

1) 

2) 

3) 

4) 

 

코드

(C언어)

solution 1)

solution 1

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(C++)

solution 1)

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    int answer = 0;
    std::vector<int> v = {1,2};
    if (n == 1)
        return 1;
    for (int i = 2; i < n; ++i)
    {
        int tmp = v[i-2] + v[i-1];
        v.push_back(tmp % 1000000007);
    }
    answer = v[n-1];
    return answer; 
}

solution 2)

#include<>

solution 3)

#include<>

 

(C#)

solution 1)

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(Java)

solution 1)

- N: 가로의 길이

- 가로 길이가 1 또는 2인 경우: O(1)

- 반복문은 N - 2번 수행: O(N)

- 최종 시간 복잡도: O(N)

class Solution {
    public int solution(int n) {
        // 동적계획법을 위한 배열 초기화
        // dp[i]는 가로 길이가 i일 때 바닥을 채우는 방법의 수
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        
        // 가로 길이가 3부터 n까지의 각각의 경우에 대해 바닥을 채우는 방법의 수를 구함
        for (int i = 3; i <= n; ++i) {
            // dp[i] = dp[i - 1] + dp[i - 2]
            dp[i] = (dp[i - 1] + dp[i - 2]) % 1_000_000_007;
        }
        // 바닥의 가로 길이가 n일 때 바닥을 채우는 방법의 수인 dp[n]을 반환
        return dp[n];
    }
}

solution 2)

#include<>

solution 3)

#include<>

 

(Python)

solution 1)

- N: 가로의 길이

- 가로 길이가 1 또는 2인 경우를 처리: O(1)

- 반복문은 N - 2번 수행: O(N)

- 최종 시간 복잡도: O(N)

def solution(n):
    # 바닥의 가로 길이가 1인 경우, 바닥을 채우는 방법의 수는 1
    if n == 1:
        return 1
    
    # 바닥의 가로 길이가 2인 경우, 바닥을 채우는 방법의 수는 2
    if n == 2:
        return 2
    
    # 동적 계획법을 위한 리스트 초기화
    # dp[i]는 가로 길이가 i일 때 바닥을 채우는 방법의 수
    dp = [0] * (n + 1)
    dp[1] = 1
    dp[2] = 2
    
    # 가로 길이가 3부터 n까지의 각각의 경우에 대해 바닥을 채우는 방법의 수를 구함
    for i in range(3, n + 1):
        # dp[i]는 dp[i-1]과 dp[i-2]를 더한 값
        dp[i] = (dp[i-1] + dp[i-2]) % 1000000007
    # 바닥의 가로 길이가 n일 때 바닥을 채우는 방법의 수인 dp[n]을 반환
    return dp[n]

solution 2)

def solution(n):
    answer = 0
    a, b = 1, 2
    for i in range(1, n):
        a, b = b, (a+b)%1000000007
    return a

solution 3)

import

 

(JavaScript)

solution 1)

- N: 가로의 길이

- 가로 길이가 1 또는 2인 경우: O(1)

- 반복문은 N - 2번 수행하므로 O(N)

- 최종 시간 복잡도: O(N)

// 시간 초과 문제
function solution(n) {
    // 바닥의 가로 길이가 1인 경우, 바닥을 채우는 방법의 수는 1
    if (n === 1) {
        return 1;
    }
    
    // 바닥의 가로 길이가 2인 경우, 바닥을 채우는 방법의 수는 2
    if (n === 2) {
        return 2;
    }
    
    // 동적 계획법을 위한 배열 초기화. dp[i]는 가로 길이가 i일 때 바닥ㅇ르 채우는 방법의 수
    const dp = Array(n + 1).fill(0);
    dp[1] = 1;
    dp[2] = 2;
    
    // 가로 길이가 3부터 n까지의 각각의 경우에 대해 바닥을 채우는 방법의 수를 구함
    for (let i = 3; i <= n; ++i) {
        // dp[i]는 dp[i-1]과 dp[i-2]를 더한 값
        dp[i] = (dp[i - 1] + dp[i - 2]) %1000000007;
    }
    
    // 바닥의 가로 길이가 n일 때 바닥을 채우는 방법의 수인 dp[n]을 반환
    return dp[n];
}


function solution(n) {
    let a = 1;
    let b = 2;

    for (let i = 2; i < n; i += 1) {
        const temp = b;
        b = (a + b) % 1000000007;
        a = temp;
    }

    return b;
}

solution 2)

import

solution 3)

import