DP 정복 - 4.2 다이내믹 프로그래밍을 사용한 문제 해결 : 예제 풀기 1

DP를 이용한 첫 번째 예제는 '타일로 공터 채우기' 다.

 

BOJ에 동일한 문제가 올라와 있어서 링크도 남김.

https://www.acmicpc.net/problem/11726

 

책에서 제시한 풀이법은 다음과 같다.

1. 첫 번째 타일을 세로로 배치하면 2 x (n-1) 크기의 공터에 타일을 배치하는 경우의 수로 문제가 재정의 됨

2. 첫 번째 타일을 가로로 배치하면 2 x (n-2) 크기의 공터에 타일을 배치하는 경우의 수로 문제가 재정의 됨.

 

그러므로 종료 조건은

1. n=1이면 세로로 한 개의 타일 놓는 법 밖에 없음.

2. n=2이면 타일을 가로로 2개 놓거나 세로로 2개 놓는 법 밖에 없음.

 

위의 내용을 그대로 코드로 옮기면 다음과 같다.

import sys
sys.setrecursionlimit(10**5)

def solve(n):
    if n == 1:
        return 1
    if n == 2:
        return 2

    return solve(n - 1) + solve(n - 2)

if __name__ == '__main__':
    n = int(input())
    print(solve(n) % 10007)

문제는 n이 커지면 커질수록 시간 및 공간 복잡도가 늘어나기 때문에

메모이제이션을 해서 해당 이슈를 좀 줄여보도록 하자. (여기서부턴 내가 짠 소스)

 

import sys

sys.setrecursionlimit(10 ** 5)

dp = [0, 1, 2] + [-1 for _ in range(1000)]


def solve(n):
    if dp[n] != -1:
        return dp[n]

    dp[n] = solve(n - 1) + solve(n - 2)
    return dp[n]


if __name__ == '__main__':
    n = int(input())
    print(solve(n) % 10007)

어라..? 이게.. 되네...?? ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

제출을 했더니 가뿐하게 통과!!

(참고로 피보나치수열의 메모 이제이 션 예를 책에서 찾아서 구현했다.)

 

이제 이 소스를 다이내믹 프로그래밍 소스로 바꿔 보았다.

import sys

sys.setrecursionlimit(10 ** 5)

dp = [0, 1, 2] + [-1 for _ in range(1000)]

if __name__ == '__main__':
    n = int(input())

    for i in range(3, 1001):
        dp[i] = (dp[i - 1] + dp[i - 2]) % 10007

    print(dp[n])

오.. 이것도 되네?? ㅋㅋㅋㅋㅋㅋㅋㅋ

 

문제가 도형으로 설명돼서 그렇지 '피보나치수열'의 값을 구하는 거랑 크게 차이가 없는 소스였다.

 

뭔가 기본을 배운 것 같은 느낌적인 느낌?

내일 풀어볼 예제도 이렇게 술술 풀렸으면 좋겠다.