취준생의 코딩테스트 연습기

[백준] 1904번 01타일 / 파이썬(python) 본문

코딩테스트/백준

[백준] 1904번 01타일 / 파이썬(python)

Jiwon_C 2021. 3. 16. 01:43

# 문제 링크

www.acmicpc.net/problem/1904

 

1904번: 01타일

지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이

www.acmicpc.net

# Soultion(실패)

메모리 초과문제로 실패하였다.

1
2
3
4
5
6
7
8
# 메모리 초과
n = int(input())
 
li = [1,2]
 
for i in range(2,n):
    li.append((li[i-1]+li[i-2]))
print(li[n-1]%15746)
 cs

 

# Soultion(성공)

리스트에 저장할 때, 너무 큰 수를 넣어서 메모리초과문제가 발생하여15746을 나눈 나머지를 출력하는 방식이 아닌, 리스트에 저장할때 나머지를 저장하는 방식으로 변경

1
2
3
4
5
6
7
8
 
n = int(input())
 
li = [1,2]
 
for i in range(2,n):
    li.append((li[i-1]+li[i-2])%15746)
print(li[n-1])
 cs

 

이 문제는 피보나치수열과 똑같이 점화식을 이용하여 푸는 문제이다.

수열은 1,2,3,5,8과 같은순서로 증가한다.

따라서 재귀함수를 이용하여 문제를 풀게되면 시간이 오래걸리기때문에, for문을 이용하여 간단하게 구현

'코딩테스트 > 백준' 카테고리의 다른 글

[백준] 11048번 파도반 수열 / 파이썬(python)  (0) 2021.03.20
[백준] 9461번 파도반 수열 / 파이썬(python)  (0) 2021.03.16
[백준] 9184번 신나는 함수 실행 / 파이썬(python)  (0) 2021.03.14
[백준] 1003번 피보나치 함수 / 파이썬(python)  (1) 2021.03.14
[백준] 9663번 N-Queen / 파이썬(python) - 도전중  (0) 2021.03.13
'코딩테스트/백준' Related Articles more
Comments