115dkk   1년 전

다음과 같은 코드를 짜서 조금씩 바꿔 시도해봤으나 계속 틀립니다.


중복되는 무게가 있을 때의 올바른 해결책은 무엇인가요?

zlzmsrhak   1년 전

이 문제의 경우 답을 구하는 단계(52~57번째 줄)과 공을 추가하는 단계(51번째 줄)로 나누어져 있습니다.

무게가 같은 공들에 대해서, 각각의 답을 구한 후, 한꺼번에 추가하는 방식으로 진행해야 합니다.

아마 아래 코드처럼 진행될 것 같습니다.


추가로, s 배열 크기가 1 작습니다.

115dkk   1년 전

그렇게 접근하면 O(N2)이 되어 시간초과납니다. (입력 개수 최대 20만*탐색 횟수 최대 10만=200억=시간 초과)

다른 방법이 없을까요...

zlzmsrhak   1년 전

?!? 저 코드는 O(N)인데요..

115dkk   1년 전

저는 소스 코드를 다음과 같이 수정해서 사용하였습니다. (참고로 저는 1~2번에서 [0]을 미리 더한채 시작했기 때문에 i는 1부터 시작하고, 님과 같은 순서대로 for문을 진행하면 오답이 되므로 8~10번을 뒤집어놨습니다. int j는 중복선언이기 때문에 그대로 때려박을 경우 컴파일 에러가 일어나 삭제했습니다.)


그런데 이 방법으로 해결을 시도하면 시간 초과가 발생합니다. O(N)일 경우, 최대 20만의 탐색횟수이므로 시간 초과가 날 수 없는 문제입니다.


이는 이 알고리즘이 O(N)을 초과하는 복잡도를 요구하거나, 어딘가 시간을 잡아먹는 부분이 있다는 의미입니다. O(N2)이라는 것은 제가 섣불리 판단한 것 같습니다. 죄송합니다.


참고로 저는 iostream (cin/cout) 안씁니다. 즉, 입출력 때문에 동작 속도가 지연된 것은 아닙니다.

115dkk   1년 전

아, 댓글 내용이 수정되지 않는군요.

for문 진행을 님 식으로 뒤집어 놨는데, 틀렸다고 나오진 않고 시간초과만 튀어나옵니다. 

그리고 생각해보니 님 식이 맞는 것 같습니다.(같은 무게일 경우 일단 더하지 말고 결과부터 계산하는게 맞을 테니까요.)

하지만 시간 초과는 왜 생기는지 모르겠습니다...


참고로 j-- 코드를 뺄 경우 오답이 발생합니다. 어떤 이유인지는 기억나지 않지만...

zlzmsrhak   1년 전

너무 오래 되서 기억은 잘 나지 않지만 수정한 부분이 꽤 되었던 것 같습니다.

확인해보세요

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