ktjooho   6달 전

해설 슬라이드를 참고해서, O(N^2) 으로 수행되는  알고리즘을 작성 했는데요.

값이 클 경우에는 답이 틀리게 나오네요. 몇 시간째 붙들고 있는데.. 도무지 어디가 잘못 되었는지 확인이 잘 안되네요.

N^3에서 N^2으로 줄인 방식은,

이전 인덱스에서 SUM이 음수값이 나오는 구간은 다음 인덱스에서 나타나는 SUM 값에 영향을 미치지 않으므로,

다음 인덱스에서 나타날 수 있는, 모든 SUM 값에 각각 경우의 수를 더하구요.

그 다음에 이전 인덱스에서 SUM이 양수값이 나오는 구간에는 다음 인덱스에 나타는  SUM 값에 영향을 미치 않습니다.

그래서 여기에 대해서는 특정 SUM 값들을 뽑아야 되는데요. 

여기서는 더해지는 패턴에 대해서 행렬로 그려보니깐 대각선 형태로 더해지는 패턴으로 나오길래, 연속되는 대각선의 값을 더하는 형식으로 구했습니다. 

샘플 테스트 케이스에서는 답이 제대로 나왔습니다.

그런데 제가 만든 특정 케이스, 가령,

1

4 500

-1000 1000

-1000 1000

-1000 1000

-1000 1000

큰 값이 나오는 경우에서는 N^3 알고리즘과는 상이한 결과가 나오더라구요. 

코드 첨부합니다. 

확인해주시면 감사하겠습니다.

수고하세요!




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