tryotto   4년 전

메모이제이션을 따로 쓰지도 않았고

따로 DP 배열을 만들지도 않고

단순히 반복문만 돌렸는데 AC가 나왔는데


혹시 숨겨진 의도가 있나요?

DP로 풀 만한 이유가 있나요?

가르침이 필요합니다 ㅜ

leo5469   4년 전

사실 해당 문제는 디피로 풀기 다소 까다로운 부분은 있지만 이런식으로 풀 수는 있죠. 어짜피 한번 계산 되었던 케이스의 답은 이후 나올 케이스의 부분 문제가 될 수 있으니 한번 계산할 때 중간 결과 값을 모두 메모이제이션을 하는 겁니다. 그런데 전역으로 디피를 위한 10만 길이의 배열을 사용할 경우, 각 배열 요소의 이 10만을 넘을 수 있기 때문에 런타임 에러가 뜰겁니다. 그래서 10만을 넘어가는 경우는 배열을 사용하지 않는 로직을 추가하거나 혹은 코드와 같이 map을 사용해서 할수도 있구요. 후자의 경우에는 메모리도 시간효율도 워낙 안좋기 때문에 단순 반복문으로 돌리는 것이 훨씬 빠를 겁니다.

댓글을 작성하려면 로그인해야 합니다.