[Python] 백준 풀기 1904 - 01타일

파이썬 백준 1904번

실버3

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

1904번: 01타일

 

 

 

 

문제 보기

처음에는 00 타일을 하나로 묶어 가짓수를 줄여 생각해야 했는데, 힌트를 찾다 보니 피보나치 수열을 갖는 문제였다.

문제의 형태를 피보나치 수열로 이해를 해야 하는데 이 부분 접근이 쉽지 않았다.

아래의 그림을 통해 이해한 부분을 정리 하였다.

 

 

 

문제 풀기

이해의 핵심 부분으로는 N 이 증가하면서 타일이 오른쪽으로 하나씩 늘어나는데, 이 맨 오른쪽 타일 (빨간색) 을 00 으로 붙은 타일과 1 하나로 이루어진 타일의 두 경우로 나누어 생각하면 된다.

이렇게 두 경우를 나누게 되면 맨 오른쪽의 00 또는 1 을 제외한 왼쪽의 타일들은 이미 이전전번째 (N-2) 와 이전번째 (N-1)에 출현을 했던 경우이다.

 

N = 1 과 N = 2 는 규칙에서 제외하고 경우의 수로 따져보면,

Case(N = 1), 1 가지

Case(N = 2), 2 가지

 

Case(N = 3), 1 + 2 가지

Case(N = 4), 2 + 3 가지

Case(N = 5), 3 + 5 가지

     .

     .

Case(N), Case(N - 2) + Case(N - 1) 가지

 

로 설명이 된다.

 

따라서,

case_ls[i] = (case_ls[i - 2] + case_ls[i - 1])

형태의 피보나치 수열과 같은 코드로 이미 실행된 경우에 대해 지속적으로 저장하여 재귀 함수와 달리 빠른 연산을 할 수 있다.

문제에서 제시한 15746 로 나누어 나머지만 표기하도록 하였는데 이는 점점 더 커지는 경우의 숫자들에 대해 구간 제한을 걸기 위한 것으로 보인다.

 

 

 

 

코드 보기

import sys
inputdata = sys.stdin.readline

N = int(inputdata().strip())
case_ls = [None] * 1_000_001

case_ls[1] = 1
case_ls[2] = 2

for i in range(3, N + 1):
    case_ls[i] = (case_ls[i - 2] + case_ls[i - 1]) % 15746
    
result = case_ls[N]
print(result)



# 999999

# 15745

문제에서 제시한 N 의 범위만큼 리스트 case_ls = [None] * 1_000_001 를 생성.

초기값이 될 N = 1, N = 2 의 값을 지정.

case_ls[1] = 1
case_ls[2] = 2

3 부터 N 이 될 때까지 for 문을 돌리면서 

case_ls[i] = (case_ls[i - 2] + case_ls[i - 1]) % 15746

를 계산하여 리스트에 넣음.

 

 

 

 

 

추가 하기

import sys
inputdata = sys.stdin.readline

N = int(inputdata().strip())
case_ls = [None] * 16

case_ls[1] = 1
case_ls[2] = 2

for i in range(3, N + 1):
    case_ls[i] = (case_ls[i - 2] + case_ls[i - 1]) % 10
    print(case_ls)
    
result = case_ls[N]
print(result)



# 15

# [None, 1, 2, 3, None, None, None, None, None, None, None, None, None, None, None, None]
# [None, 1, 2, 3, 5, None, None, None, None, None, None, None, None, None, None, None]
# [None, 1, 2, 3, 5, 8, None, None, None, None, None, None, None, None, None, None]
# [None, 1, 2, 3, 5, 8, 3, None, None, None, None, None, None, None, None, None]
# [None, 1, 2, 3, 5, 8, 3, 1, None, None, None, None, None, None, None, None]
# [None, 1, 2, 3, 5, 8, 3, 1, 4, None, None, None, None, None, None, None]
# [None, 1, 2, 3, 5, 8, 3, 1, 4, 5, None, None, None, None, None, None]
# [None, 1, 2, 3, 5, 8, 3, 1, 4, 5, 9, None, None, None, None, None]
# [None, 1, 2, 3, 5, 8, 3, 1, 4, 5, 9, 4, None, None, None, None]
# [None, 1, 2, 3, 5, 8, 3, 1, 4, 5, 9, 4, 3, None, None, None]
# [None, 1, 2, 3, 5, 8, 3, 1, 4, 5, 9, 4, 3, 7, None, None]
# [None, 1, 2, 3, 5, 8, 3, 1, 4, 5, 9, 4, 3, 7, 0, None]
# [None, 1, 2, 3, 5, 8, 3, 1, 4, 5, 9, 4, 3, 7, 0, 7]
# 7

개인적으로 코드의 작동을 이해하기 위해 print(case_ls) 를 추가해 보았다.

위의 결과는 N = 15 일 때, case_ls 를 16 개로 제한하고 경우의 수를 10으로 나누었을 때 결과이다.