moonsoo5522   2달 전

점화식은 이렇게 정의했습니다. 

dp[i][j] = 수열을 j등분했을때 첫번째 인덱스가 i일 경우의 최대값


19~22라인에서 범위를 나누는 재귀를 타고

25라인에서는 나누지않고 연속합을 리턴값으로 넘겨받아서 더하도록 작성했습니다.



제가 임의로 넣어본 테스트 케이스에서는 모두 제대로 작동했었고

계속 오답 나오더니 이제 갑자기 시간 초과가 뜨네요...


if ((N - idx - 1) / 2 < n-1) return INF;

이 코드를 이용해 해가 나올 수 없는 경우를 건너뛰면 시간초과는 면하는데 결국 오답..ㅠㅠ



////////////////////////////////////////////////////////////////////////////////////////////////////////////


해결했습니다..... 그냥 테스트케이스 생성기 하나 만들고, 구글링해서 얻은(ㅎㅎ) 솔루션 코드랑 실행결과 비교해가면서 확인해보니,  value2부분 최대값 비교하는 부분이 틀렸고, 자잘한 예외처리 몇개 해주니까 되네요.

정신건강 상 솔루션 코드를 분석해보는게 더 좋을거 같아요... 예외처리 여기저기 하니까 더러워지네요.


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