ll1000wooll   5달 전

캐쉬배열을 제일 첫단어 인덱스, 빈칸의 갯수 형식으로 메모이제이션해서

빽트랙킹 돌렸습니다..

TC 만들어서 캐쉬 제대로 태우는지 다 일일이 확인해봤는데도 도무지 틀린답을 못찾겠습니다 ㅠ.ㅠ

도와주십시용ㅠㅠㅠㅠㅠ

zlzmsrhak   5달 전

먼저 반례는

3 7

1

1

3

답: 0


1. 제가 코드를 보기에는 캐시 배열이 check[첫 단어 인덱스][끝 단어 인덱스] 인 것 처럼 보입니다.

10번째 줄의 종료 조건이 (두 값의 합이 n과 같다)인 것이나, 24번째 줄 start_point가 (두 값의 합) + 1 인 것을 보면요..

제가 보기엔 적어도 빈 칸의 갯수는 아닌 것 같습니다.


2. 26번째 줄에서 cnt 값이 늘어나는데도 불구하고 total에 cnt 값을 계속 누적시켜서 잘못된 값을 가지고 있을 거 같은 느낌이 듭니다.

3. 지금 코드 시간복잡도는 O(N^3)이기 때문에 최적화를 해야 될 것 같습니다.

4. 메모이제이션은 백트래킹이라고 안합니다.

ll1000wooll   5달 전

상세한 답변 감사드립니다.

처음 알고리즘을 짤때 cnt는 빈칸이 들어가는 갯수로 생각하고 구현을 하였습니다ㅠㅠ

첫단어 인덱스 + cnt 의 경우 첫 인덱스에서 빈칸 갯수를 더해줌으로 끝인덱스라고 볼수도 있겠군요! 

2번에서 말씀해주신 문제점을 디버깅 해보니 cnt 값이 계속 누적된 문제점이 맞았습니다.

나머지 지적해주신 부분도 숙지하도록 하겠습니다 감사합니다^^

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