2467번 - 용액
용액문제에서.. 시간초과가 뜹니다..!ㅠㅠ
이래저래 고쳐서 테스트하였더니 78%까지 체점되다가 그 이후에 시간초과가 뜨네요.
오름차순으로 숫자가 입력되는 것을 감안해,
오른쪽 숫자부터 비교하도록 하였고 두 수의 합이 더 작아지지 않는다면 break 로 다음 수를 비교하도록 하였습니다.
그리고 0이 가장 최소값이므로 0이면 바로 정답을 출력하도록 했고..
양쪽 숫자의 합이므로, 이미 방문한 숫자는 빼도록 하였습니다.
시간을 더 줄일 수 있는 방법이 무엇이 있을까요..?
조언 부탁드립니다.^^
하나를 정하고 이진 검색으로 지금 break 걸리는 부분을 O(logN)에 찾을 수 있습니다.
안쪽 for문을 이진 검색으로 대체하면 O(NlogN) 에 해결 되겠네요.
아! 그렇군요ㅎㅎ감사합니다.
댓글을 작성하려면 로그인해야 합니다.
ehdwns2045 5년 전
용액문제에서.. 시간초과가 뜹니다..!ㅠㅠ
이래저래 고쳐서 테스트하였더니 78%까지 체점되다가 그 이후에 시간초과가 뜨네요.
오름차순으로 숫자가 입력되는 것을 감안해,
오른쪽 숫자부터 비교하도록 하였고 두 수의 합이 더 작아지지 않는다면 break 로 다음 수를 비교하도록 하였습니다.
그리고 0이 가장 최소값이므로 0이면 바로 정답을 출력하도록 했고..
양쪽 숫자의 합이므로, 이미 방문한 숫자는 빼도록 하였습니다.
시간을 더 줄일 수 있는 방법이 무엇이 있을까요..?
조언 부탁드립니다.^^