iljimae   2년 전

문제:  N과 L이 주어질 때, 합이 N이면서, 길이가 적어도 L이면서 가장 짧은 연속된 음이 아닌 정수 리스트를 구하는 프로그램을 작성하시오.


이 문제를 해결하기위해 부분합 배열 psum[]을 먼저 채워넣고 어떤 범위 [a,b] 사이의 값들을 모두 더했을때 N이 되기위해서는 psum[b]-psum[a-1] = N 을 만족해야하니까 모든 a 에 대해서 (a의 범위 0~50000, 0 일때는 예외처리) psum[a-1]+N 이 psum[] 에 존재하는지 이진탐색으로 확인하는 방법을 사용했는데 4% 정도에서 틀립니다. 뭐가 틀렸는지 알려주실 수 있나요? 아니면 반례 데이터를 주셔도 됩니다. 감사합니다! 

koosaga   2년 전

999999999 2 를 생각해보세요

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