[백준] 11726번 DP - 파이썬 (오버플로우)

백준 11726

 

백준 11726번 타일링 문제입니다.

 

DP 문제의 특징은 전에 계산된 식의 결과값을 다시 사용함으로써 메모리 효용성을 기대하는 것이죠.

 

그래서 문제에 대한 반복적인 규칙을 찾아

점화식을 만들어 푸는 방법으로 접근해야합니다.

 

문제 분석

$2*n$ 크기의 직사각형을 $1*2$ 혹은 $2*1$ 의 타일로 채우는 방법은 두 가지 경우의 수로 나눌 수 있습니다.

1. 마지막 직사각형이 $1*2$ 타일이 한 개 들어가는 경우
2. 마지막 직사각형으로 $2*1$ 타일이 두 개 들어가는 경우

 

첫 번째 경우는 마지막은 $1*2$ 타일로 놓고, $2*(n-1)$ 크기의 직사각형을 채우는 방법의 수와 같죠.

두 번째 경우는 마지막에 타일이 두 개가 들어가기 때문에 $2*(n-2)$ 크기의 직사각형을 채우는 방법의 수와 같아집니다.

 

그럼 이걸 계속해서 점화식으로 채우면

 

dp[n] = dp[n-1] + dp[n-2]

 

로 나타낼 수 있습니다.

 

그럼 먼저 $2*1$의 직사각형을 채우는 경우의 수를 볼게요.

세로의 길이가 2로 고정되어 있고, 가로의 길이가 1로 고정되어 있으므로 들어갈 수 있는 타일은 $2*1$ 오직 한 개 뿐 입니다.

dp[1] = 1

 

두 번째 경우를 봅시다.

$2*2$의 직사각형을 채워야 한다면, $1*2$ 짜리 타일을 두 개 깔 든, $2*1$ 짜리 타일을 두 개 깔 든 할 수 있습니다.

그럼 $1*2$ 타일만 쓰는 경우 1가지, $2*1$ 타일만 쓰는 경우 1가지 해서 총 2가지 경우의 수가 됩니다.

dp[2] = 2

 

그럼 앞에서 점화식을 생각했기 때문에 n이 3이상인 경우에는 직사각형에 끝에 세로로 긴 타일이 온다면 끝에 타일하나를 고정하고 $2*2$ 크기의 직사각형을 채우는 경우의 수를 생각할 수 있습니다. 위에서 확인했듯이 값은 dp[2] = 2가 되겠죠.

 

또 다른 경우로 가로로 긴 타일을 두개 배치해야 한다면 뒤에 타일 두개를 고정하고 $2*1$크기의 직사각형을 채우는 경우의 수만을 생각해 볼 수 있습니다. dp[1]의 값이 되겠네요.

 

본 점화식을 만족하기 때문에,

점화식을 바탕으로 코드를 짜줍니다.

 

정답 코드

n = int(input())

dp = [0] * (n+1)

dp[1] = 1

if n > 1 : 
    dp[2] = 2

# 1*2 타일을 마지막에 놓는 경우, 2*(n-1) 크기의 직사갹형을 채우는 방법의 수와 같다.
# 2*1 타일을 마지막에 놓는 경우, 2*(n-2) 크기의 직사각형을 채우는 방법의 수와 같다.

# dp[n] = dp[n-1] + dp[n-2]

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

print(dp[n])

 

처음에는 dp[1] = 1, dp[2] = 2를 두고 배열값을 지정해두었으나,

n = 1 이 입력되는 경우, 인덱스 값은 1까지 밖에 돌지 않는데 dp[2] = 2를 지정하게 되니, 인덱스 오류가 발생하게 됩니다.

 

따라서 조건문을 생성하여

n 이 1보다 큰 경우를 고려해주도록 하였습니다.

 

그리고 n이 3이상인 경우,

반복문을 이용하여 점화식을 적용하였습니다.

 

 

오버플로우

이 문제는 오버플로우를 주의해서 풀이해야 합니다.

 

각 데이터 타입의 변수들은 고정된 크기의 비트로 구성됩니다.

즉, 담을 수 있는 양이 정해진 방들인 것이죠.

예를 들어 32비트 정수(int)형 변수의 경우 최대 $2^{32}-1$의 값을 가질 수 있습니다.

표현할 수 있는 숫자가 $2^{32}-1$ 까지인 것이죠.

 

따라서 이 변수에 표현할 수 있는 한계 숫자보다 더 큰 값을 저장하게 되면 양의 오버플로우가 발생해 -2,147,483,648 이 출력됩니다. (표현할 수 있는 가장 첫 번째 값으로 돌아감) 반대로 표현할 수 있는 한계 숫자보다 더 작은 값을 저장하게 되면 음의 오버플로우가 발생해 오히려 가장 큰 양수값이 출력되는 결과를 초래할 수 있는 것이죠.

 

Python의 경우는 정수형이 사용가능한 메모리가 허용하는 한 어떠한 크기의 숫자도 저장할 수 있도록 설계 되어 오버플로우가 발생하지 않지만, JAVA, C++과 같은 다른 언어들의 경우 정수형을 담을 수 있는 공간이 보다 작아 작은 숫자 범위내에서만 표현이 가능합니다.

 

따라서 작은 범위내에서만 계산되도록 이 문제에서는 'int' 타입의 범위 내에서 연산을 안전하게 수행하도록 10007로 나눈 나머지를 구하여 출력하도록 명시하였습니다.

 

출력시 print 구문에서 %10007을 해 줄 수도 있지만,

파이썬을 제외한 다른 언어들에서는 dp 배열 계산이 이뤄지는 점화식 과정에서 오버플로우가 발생해 문제의 결과값이 달라질 수 있으므로 점화식 자체에서 애초에 %10007을 계산하여 저장해주는 것이 좋습니다.