[다이나믹 프로그래밍] ▲ 1904번 - 01타일

[백준] 1904번 - 01타일

(한줄평) 아이디어는 쉽게 떠올렸으나 오류를 고치는데 시간이 걸렸던 문제! 나중에 다시 한 번 풀어봐야할 것 같다

(풀이1) 틀린 코드

풀이 시간: 20분 이내

1) 문제 해결 아이디어

1이상 1000000이하인 길이 n인 모든 2진 수열의 개수를 15746으로 나눈 나머지를 구하는 문제다.

 

<00, 1로 나타내기 위한 경우의 수>

<점화식>

첫번째 오류. 메모리 초과

dp테이블의 크기를 n만큼 생성했는데 최대값이 1000000인 탓에 메모리 초과가 난 것 같다.

그래서 리스트를 사용하지 않고 값 2개를 저장할 수 있는 변수 2개(a, b)를 생성하여 문제를 해결했다.

 

두번째 오류. 시간초과

1%까지 되다가 시간초과가 났다. 15746으로 나눈 나머지를 출력시켜야 하는데 그냥 그 값을 출력시키도록해서 생긴 문제였다.

 

세번째 오류. 런타임 에러(IndexError)

아래 코드처럼 작성하면 100%까지 잘 되다가 런타임 에러가 뜬다..

계속하다가 도저히 이유를 모르겠어서 찾아봤는데,, n이 1일 때 문제가 발생하는 것이었다..

n이 1이면 d[1]에 값을 대입할 수가 없다... 이런 오류를 막기 위해서 애초에 dp테이블의 크기를 1000000으로 생성해야한다!!

 

2) 소스코드

n = int(input())  # 2진 수열 크기
d = [0] * n
d[0], d[1] = 1, 2
for i in range(2, n):
  d[i] = (d[i-1] + d[i-2]) % 15746
print(d[n - 1])

 

(풀이2) 성공 코드

풀이 시간: 20분 이내

1) 문제 해결 아이디어

 

2) 소스코드

n = int(input())  # 2진 수열 크기
d = [1, 2]
for i in range(2, n):
  d.append((d[i - 1] + d[i - 2]) % 15746)
print(d[n - 1])