[백준 파이썬] # 1904 01타일

Silver III

# 1904 01타일

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

1904번: 01타일

 

풀이

N = int(input())
dp = [0] * (N+1)  # indexerror 방지
dp[0] = 1
dp[1] = 2
for i in range(2, N):
    dp[i] = (dp[i-2] + dp[i-1]) % 15746  # 메모리 크기 제한
print(dp[N-1])

 

후기

• 백준에서 문제 검색 버튼을 이용하면 에러가 발생하는 원인에 대해 쉽게 검색할 수 있다
  (이걸 이제 알았다니.. 원인을 모르는 오답이 발생할 때 구글링 말고 문제 검색을 이용하자)
  
  
• 00 타일을 묶어 O으로 바꿔보면 N > 3일 때, OX를 배치하는 경우의 수 문제와 같아진다. 이를 이용해 피보나치 수열이라는 점을 알아낼 수 있고, N번째 값을 찾을 수 있다.
  
  • ex) N=5일 때 - 00(O),1배치 → 8개
    1이 1개) OO1, O1O, 1OO : 3
    1이 3개) O111, 1O11, 11O1, 111O : 4
    1이 5개) 1111 : 1
    
    
• 메모리 초과 : 파이썬의 int형이 고정된 크기가 아니기 때문에, 수가 커지면 커질 수록 더 많은 메모리를 필요로 하게 된다. 계산된 값을 특정 값으로 나눠주게 되면(ex : %15746) 크기를 제한할 수 있어서 메모리를 제한할 수 있게 된다
  
  
• '이 문제와 같이 "~로 나눈 나머지를 출력한다"는 문제는 거의 대부분 전체 답을 먼저 구하고 마지막에 나머지 연산을 한 번 하라는 것이 아니라, 연산 과정에서 모듈로의 성질을 이용하여 수를 계속 작게 유지할 수 있도록 배려를 해주는 것입니다. 안 그러면 수가 너무 커져서 계산 시간도 오래 걸릴 뿐만 아니라 파이썬처럼 bigint를 지원하지 않는 언어에서는 구현하는 것 자체가 매우 까다롭기 때문입니다.' - djm03178 님 해설
  
  
• indexterror : N이 1일 때 dp[1] = 2가 적용되지 못해서 생기는 오류이다. dp를 N+1 크기로 설정해주면 N이 1일때 발생하는 오류를 해결할 수 있다.

 

---

순열, 조합 이론 적용해서 규칙 구하기

N=5일 때, O(00)과 1을 3개의 공간에 배치 = 3+4+1 = 8 

• 1이 1개일 때 : OO1 → 3!/2!*1! = 3
• 1이 2개일 때 : O111 → 4!/3!*1! = 4
• 1이 3개일 때 : 1

2022.02.15 - [Algorithm Study/이론] - [확률과 통계] 순열과 조합