728x90
반응형
문제 출처: https://www.acmicpc.net/problem/1904
1904번: 01타일
지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이
www.acmicpc.net
풀이:
먼저 규칙을 알아보기위해 중복순열을 사용하였다
from itertools import product
# 길이가 1부터 5까지에 규칙을 알아보기 위해서 1부터 5까지 딕셔너리 생성
number_dic = {i:0 for i in range(1,6)}
lst = ['00','1']
for z in range(1,6): # 1부터 5까지
for i in product(lst, repeat=z): #중복으로 z갯수만큼 사용해서 만든다.
x = ''.join(i) # list에 따로 담기니깐 join으로 합쳐주고
if len(x) in number_dic: # 만약 길이를 키로 가지고있는 값이 딕셔너리에 있으면
number_dic[len(x)] += 1 # 추가해준다.
else: # 없다면
pass # 그냥 지나친다
# 위 코드를 돌리면
{1: 1, 2: 2, 3: 3, 4: 5, 5: 8} 출력
규칙성을 보면 dp 처음배울때 dp[i] = dp[i-1] + dp[i-2] 다
제출용 코드 (정답)
def dp(n):
dp = [0] *1000001
dp[1],dp[2] = 1, 2
for i in range(3,n+1):
dp[i] = (dp[i-1] + dp[i-2]) % 15746
return dp[n]
print(dp(n))15746 으로 나눠주지않으면 메모리 초과 나옴
반응형
댓글