요즘은 신경치료를 받으면서 네이버 테스트를 준비 중이라 공부를 많이 못한다.
변명이 아니라 진짜 너무 스트레스받는다 치통...
나중에 이 글을 읽는 나는 명심해라! 이가 조금이라도 깨지면 바로 치과로 가라!
문제
출처 : https://www.acmicpc.net/problem/11726
이 문제를 포스팅 한 이유는 파이썬의 재귀 깊이의 한계치 때문이다.
아마 파이썬으로 이 문제를 채점하면 "런타임 에러"가 발생할 수도 있다.
문제 풀이
이 문제는 동적 프로그래밍의 가장 기본적인 문제이기 때문에 풀이는 쉽지만 그래도 정리는 해보겠다.
import sys
input = sys.stdin.readline
n= int(input())
dp = [0]*n
def f_dp(n):
if n == 1: return 1
if n == 2: return 2
if dp[n-1]: return dp[n-1]
else :
dp[n-1] = f_dp(n-1) + f_dp(n-2)
return dp[n-1]
print(f_dp(n)%10007)n을 입력으로 받으면 2x(n-1) 크기의 직사각형에 타일을 배치하는 방법의 수와 2x(n-2) 크기의 직사각형에 타일을 배치하는 방법의 수를 합치면 된다.
그 이유는
1. 공간이 2x(n-1) -> 2xn 크기로 증가할 때 2x1 크기만큼만 증가하는 경우
이 경우는 2x1 크기의 타일이 한 개 들어가는 경우밖에 없기 때문에 2x(n-1) 크기의 직사각형에 타일을 배치하는 방법의 수만큼만 더해주면 된다.
2. 공간이 2x(n-2) -> 2xn 크기로 증가할 때 2x2 크기만큼만 증가하는 경우
이 경우는 2x1 크기의 타일이 두 개가 들어갈 수 있다. 하지만 타일은 세워서 배치하는 경우 1번과 겹치는 경우이기 때문에 계산하지 않는다. 따라서 2x1 타일이 가로로 두 개 배치되는 경우만 고려하면 된다.
3. 공간이 2x(n-3) -> 2xn 크기로 증가할 때 2x3 크기만큼만 증가하는 경우
1, 2번의 경우와 중복되기 때문에 고려하지 않는다.
내가 공부하는 내용을 정리해두는 포스트여서 따로 그림은 없지만, 취업하게 되면 다른 사람들도 볼 수 있게 나도 예쁘게 정리를 해놔야겠다. 약속!
하지만 위 코드로만 결과를 제출하면 "런타임 오류"를 만나게 된다.
그 이유는 파이썬의 재귀 깊이 한계치가 작아서 오류가 발생하기 때문인데, 한 줄만 추가하면 해결이 가능하다.
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
n= int(input())
dp = [0]*n
def f_dp(n):
if n == 1: return 1
if n == 2: return 2
if dp[n-1]: return dp[n-1]
else :
dp[n-1] = f_dp(n-1) + f_dp(n-2)
return dp[n-1]
print(f_dp(n)%10007)세 번째 줄에 임의로 한계치를 설정해 주면 문제를 해결할 수 있다.
11727번 풀이
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
n= int(input())
dp = [0]*n
def f_dp(n):
if n == 1: return 1
if n == 2: return 3
if dp[n-1]: return dp[n-1]
else :
dp[n-1] = f_dp(n-1) + 2*f_dp(n-2)
return dp[n-1]
print(f_dp(n)%10007)11726번에서 조금만 수정하면 11727번도 풀 수 있다.
11726번에서 "공간이 2x(n-2) -> 2xn 크기로 증가할 때 2x2 크기만큼만 증가하는 경우"의 경우에서 2x2 크기의 타일이 배치되는 경우가 추가되기 때문에
dp[n-1] = f_dp(n-1) + 2*f_dp(n-2) 처럼 n-2의 경우의 수를 두 배 해줘야 한다.
시험이 얼마 안 남고 이는 아파서 쉬운 문제를 위주로 감을 살리는 중이다.
빨리 취업해서 나도 예쁜 블로그 포스팅을 해야겠다.
끝!