백준 11727 : 2 * n 타일링 2 (feat. 11726 : 2 * n 타일링)

www.acmicpc.net/problem/11727

11727번: 2×n 타일링 2

 

해결 방법 : 다이나믹 프로그래밍

• 타일 길이가 1증가하여 총 길이가 n이 된 경우
  • 1. 해당 공간을 2 * 1타일 하나로 채우면 타일 길이가 n-1일때의 경우의 수와 같다.
  • 2. 그렇지 않으면 1 * 2타일 2개로 채우는 경우와 2 * 2타일로 채우는 경우, 총 2가지로 새로 생긴 부분(n)을 차지할 수 있다. 이 때는 타일 길이가 n-2일 때의 경우의 수와 새로 발생한 2가지 경우를 곱한 만큼의 경우의 수가 생긴다.
  • 점화식 : dp[n] = dp[n-1] + (dp[n-2] * 2)

 

import sys
input = sys.stdin.readline

def solution(n):
    d = [0 for i in range(0, n + 2)] # DP 테이블
    d[1], d[2] = 1, 3 # case 1, 2에 대한 초기값

    for i in range(3, n + 1): # DP
        d[i] = d[i-1] + (d[i-2] * 2)

    return d[n] % 10007

if __name__ == '__main__':
    n = int(input())
    result = solution(n)
    print(result)

 

---

 

 

www.acmicpc.net/problem/11726

11726번: 2×n 타일링

위 문제의 바로 이전 문제인 2 * n 타일링.

타일 길이가 1이 증가한 경우, 해당 위치를 2 * 1타일로 채운 경우는 동일,

외에는 1 * 2타일로 채우는 경우밖에 없으므로 

점화식이 dp[n] = dp[n-1] + dp[n-2]가 된다.

import sys
input = sys.stdin.readline

def solution(n):
    d = [0 for i in range(0, n + 2)]
    d[1], d[2] = 1, 2

    for i in range(3, n + 1):
        d[i] = d[i-1] + d[i-2]

    return d[n] % 10007

if __name__ == '__main__':
    n = int(input())
    result = solution(n)
    print(result)