[질문] 백준 9465 97퍼에서 시간초과 나는데 어디가 잘못된거임???

[익명(61.43)]

https://www.acmicpc.net/problem/9465

Baekjoon Online Judge

http://boj.kr/d4ff476c0713438b86ef77e68bfa0441

Baekjoon Online Judge

데이터 다양하게 넣어보고 있는데 시초 나는 케이스 도저히 못 찾겠어서 올려봄;;;

재귀함수 이용해서 탑다운 dp로 풀었는데 블로그 검색해보니까 접근 자체는 틀린 거 없어보이는데 왜 시간초과 나는 지 모르겠다

[익명(117.20)]

대충 90퍼대면 0~1 데이터량 적은 의외케이슨데 - dc App

[익명(pungsock)]

어차피 모든 dp를 구해야해서 탑다운시 결국 dp테이블을 전부 완성할것같은데 그래서 탑다운이 이미 구한 dp에 호출됨 2n번은 값을 구하는 유의미한 호출이고 다시2n번 이미 구한거를 다시한번 일단 호출함 합해서 대략 4n에 가깝게 호출돼서 이게 비효율적이라 판단해서 아웃시키는 테스트케이스가 있나? 함수의 호출이 아예 다른 주소로 갔다와서 오버헤드가 좀 있는건 아는데 그게 n이 10만이니 40만번쯤 호출되면 문제가 생기나? 40만 호출이 얼마나 시간영향이 있는지는 모르겠음 바텀업으로 푸니까 그냥 돌아감 - dc App

[익명(61.43)]

바텀업으로 코드 바꾸니까 바로 돌아가네... ㄱㅅㄱㅅ

[익명(223.118)]

dp 값 초기화를 0으로 하면 안됨. 잘생각해보셈

[익명(175.194)]

그러네 -1로 초기화하든지 해야했네 0초과가 아니라 0 이상이었구나

[익명(106.101)]

바로 이거였네 틀린 이유가 -1로 초기화하고 돌리니까 탑다운도 정답 뜬다 ㄱㅅㄱㅅ