백준 1904 - 동적 프로그래밍

백준 1904번 - 동적 프로그래밍

다이내믹 프로그래밍은 전체 문제를 단계 단계 별 작은 문제들로 쪼개서 스텝 바이 스텝으로 풀되, 현재 단계의 문제를 풀 때 앞에 이미 풀어놓은 부분을 활용하는 기법이라고 이해했습니다. divide and conquer 과 다른 점은 앞에 단계에서 풀어놓은 것을 뒤에 단계에서 참고하므로 작은 문제들이 서로 독립적이지 않고 겹치게 됩니다. 이전 단계의 값들을 참고하려면 이전 단계의 값들을 저장해놓아야하므로 모든 동적 프로그래밍 알고리즘은 각 단계별 값을 저장해놓는 격자로부터 시작된다고 책에 나와있었습니다.

1904번

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

어느 날 짓궂은 동주가 지원이의 공부를 방해하기 위해 0이 쓰여진 낱장의 타일들을 붙여서 한 쌍으로 이루어진 00 타일들을 만들었다. 결국 현재 1 하나만으로 이루어진 타일 또는 0타일을 두 개 붙인 한 쌍의 00타일들만이 남게 되었다.

그러므로 지원이는 타일로 더 이상 크기가 N인 모든 2진 수열을 만들 수 없게 되었다. 예를 들어, N=1일 때 1만 만들 수 있고, N=2일 때는 00, 11을 만들 수 있다. (01, 10은 만들 수 없게 되었다.) 또한 N=4일 때는 0011, 0000, 1001, 1100, 1111 등 총 5개의 2진 수열을 만들 수 있다.

우리의 목표는 N이 주어졌을 때 지원이가 만들 수 있는 모든 가짓수를 세는 것이다. 단 타일들은 무한히 많은 것으로 가정하자.

이라고 나와있었지만 결국 여러 번의 노가다를 통해 피보나치 수열 구하라는 말이구나를 알 수 있었습니다.

갖은 노가다와 고생 고생을 통한 유레카❗️

처음에는 이게 왜 동적 프로그래밍이지 싶어서 격자 에 단계별 값들을 저장해놓지 않고 그냥 더 이전 값+이전 값 한 다음에 더 이전 값은 삭제하고 더 이전 값을 이전 값으로 옮기는 방식으로 del fibo[0] 딱 이 코드 한 줄만 추가하였는데 시간 초과가 났습니다.

이를 통해서 단계별 값들을 쭉 다 저장해놓고 참고하는 동적 프로그래밍 방식으로 풀라는 말이구나를 깨달았습니다.

이번에는 동적 프로그래밍으로 풀었는데 메모리 초과 에러가 떴습니다. 이 부분부터는 뭐야 싶어서 좀 치팅을 해서 깨달았는데 첫 번째 줄에 지원이가 만들 수 있는 길이가 N인 모든 2진 수열의 개수를 15746으로 나눈 나머지를 출력한다. 에서 힌트를 얻어야했음을 알게 되었습니다.

피보나치 수열에서 값은 기하급수적으로 커지므로 21번째 값만 해도 벌써 17711입니다.

어떤 피보나치 수열 값(x) 이 15746보다 크다고 하면

x = a * 15746 + c 라고 쓸 수 있습니다. 여기서 a 는 몫이고 c 는 나머지가 됩니다.

피보나치 수열은 순차적으로 커지기만 하므로 그 다음 피보나치 값(y)도 당연히 15746보다 클 것입니다.

y = b * 15746 + d 라고 쓸 수 있습니다. 여기서 b 는 몫이고 d는 나머지가 됩니다.

x+y= a x 15746 + c + b x 15746 + d = 15746 * (a+b) + c+d 입니다.

이번에는 c+d 가 나머지일지 확실하지 않습니다. c+d가 15746보다 더 커질 수 있기 때문입니다. c+d 가 15746 보다 크다면 c+d = 15746 x f + g 라고 나타낼 수 있고 g는 나머지가 됩니다.

그러면 x+y 를 다시 써주면 a x 15746 +b x 15746 + f x 15746 + g 가 됩니다.

문제에 의하면 g 를 출력하여야합니다.

g 는 x를 15746으로 나눈 나머지 + y 를 15746 으로 나눈 나머지 를 다시 15746 으로 나눈 나머지 임을 알 수 있습니다. 즉 피보나치 수열 값이 15746 보다 커지면 값들의 나머지들로만 다시 연산해도 정상적으로 답이 나옴을 알 수 있습니다.

c+d가 15746보다 작으면 f 가 0 이 되고 g 는 c+d가 되므로 정상적으로 정답이 나옵니다.

따라서 다 계산해놓고 최종 값만 15746으로 나눈 후 나머지를 출력하지 않고 수열이 15746보다 커지는 순간부터 계속해서 나머지들끼리만 연산을 해준다면 메모리가 엄청나게 줄어들게 됩니다. (ex. 46368%15746 = 14876)

이 부분을 신경써주니까 정답을 구할 수 있었습니다.

# python3


def tile(numb):
    fibo=[0,1]
    for i in range(2,numb+2):
            fibo.append((fibo[i-2]+fibo[i-1])%15746)
           

    print(fibo[-1])


a=int(input())
tile(a)