풀이 방법은 우선 들어온 수들을 정렬합니다 O(nlogn)이기 때문에 무리없을거라 생각했구요
그리고 나서 모든 연속된 수들의 부분합을 계속 구하는 2중 for문을 사용했습니다. 문제 n조건이 크기 때문에 O(n2)으로는 풀리지 않는것을 알고있습니다. 하지만, 배열의 끝부분까지 모두 합을 구했는데도 s보다 작다면 더 진행해봐야 s보다 큰 수가 나오기 힘드니까 그냥 break;시키는 식으로 반복을 줄였습니다(정렬 되있으므로)
3%정도에서 틀리길래 풀이를 봤는데 제 풀이랑 비슷한거 같으면서도 뭔가 다르네요. 풀이를 이해하긴 해서 문제를 풀 수 있을거 같긴 한데 제 방법이 왜 틀렸는지를 알고 싶습니다. 고수분들 답변 부탁드립니다!
simsimjae 3년 전
풀이 방법은 우선 들어온 수들을 정렬합니다 O(nlogn)이기 때문에 무리없을거라 생각했구요
그리고 나서 모든 연속된 수들의 부분합을 계속 구하는 2중 for문을 사용했습니다. 문제 n조건이 크기 때문에 O(n2)으로는 풀리지 않는것을 알고있습니다. 하지만, 배열의 끝부분까지 모두 합을 구했는데도 s보다 작다면 더 진행해봐야 s보다 큰 수가 나오기 힘드니까 그냥 break;시키는 식으로 반복을 줄였습니다(정렬 되있으므로)
3%정도에서 틀리길래 풀이를 봤는데 제 풀이랑 비슷한거 같으면서도 뭔가 다르네요. 풀이를 이해하긴 해서 문제를 풀 수 있을거 같긴 한데 제 방법이 왜 틀렸는지를 알고 싶습니다. 고수분들 답변 부탁드립니다!