[BOJ] 1904 - 01타일

1904번: 01타일

어마어마하게 틀렸다.

---

문제 후기

진짜 이번 문제는 나를 너무 힘들게 했다. 하향식으로 해결하려니 재귀 제한이 걸리고, 배열을 이용해 값을 저장하는 상향식을 이용하니 메모리 초과, 그래서 계산을 풀어보니 시간 초과, 마지막 희망을 pypy3로 제출해서 드디어 맞았다. 진짜 틀릴 수 있는 모든 경우를 다 맛본듯하다.

 

문제 풀이

import sys

def makeBy(n):
    for i in range(3, n+1):
        memo[3] = memo[1] + memo[2]
        memo[1], memo[2] = memo[2], memo[3]
    print(memo[3]%15746)

if __name__ == "__main__":
    n = int(sys.stdin.readline())
    memo = [0,1,2,0]
    makeBy(n)

일단 처음에는 하향식으로 n에서 0 또는 1이 될 때까지 재귀를 사용해서 값을 계산해 리스트에 저장하는 방법으로 풀었다. 문제는 여기서 n이 커지면 재귀에 제한이 걸린다는 것. sys.setrecursionlimit()를 사용해서 재귀 제한을 늘려도 해결이 되지 않았다. 

 

그래서 전략을 상향식으로 바꾸었다. n+1의 길이를 갖는 리스트를 선언하고 각 인덱스에 계산한 값을 집어넣는 것. 이것 역시 n이 커지자 메모리를 너무 많이 잡아먹어서 다른 방법을 모색하다가... 문득, 이 문제에서는 n의 정답을 알기 위해서는 n-1과 n-2의 값만 알면 된다는 것을 알게 되었다. 그래서 처음에 a, b, c의 변수로 값을 저장하다가, 파이썬이 변수를 새로 만드는 것은 객체를 만드는 과정이라 시간과 메모리를 더 사용할 것 같다는 생각이 들었다. 그래서 최종으로 만들어낸 코드가 위에 코드이다.

 

마지막 정답 코드인 위에 코드는 길이가 4인 리스트를 만들어 초기값으로 [0, 1, 2, 0]을 갖는다. 그리고 반복문을 3부터 n까지 돌면서 memo의 1번 2번 인덱스의 값을 더해 3번 인덱스에 넣어준다. 모든 반복문을 돌면 정답을 출력.

---

글을 쓰면서 생각난 건데 이 문제는 피보나치 문제와 다를 바가 없어 보인다. 초기값만 1, 2일뿐이다. 그래서 피보나치 일반항 공식처럼 해당 문제의 일반항 공식을 구해서 그 값을 바로 계산하는 방법도 생각해보았다. 물론 루트 값이 들어가고 식 자체는 더럽겠지만 코드 자체는 더 짧아지고 어쩌면 더 빠르게 풀 수 있겠다는 생각이 들었다.

BOJ Solutions: https://github.com/Isaac-Lee/BOJ-Algorithm