2473번 - 세 용액
세 용액이 0에 가장 수렴하는 값을 찾는 문제요,
알고리즘을 설명해드리자면,
정렬된 배열에 대해서 2개의 값을 가장 작은값, 그다음 작은값, 그리고 한 값을 가장 큰 값을 지정해 놓고 시작합니다.
그렇게 해서 합이 음수냐, 양수냐에 맞춰서 배열 값들을 내리거나 올려서 최소값을 찾는 알고리즘입니다.
여기서 가장 작은 값과 그다음 작은 값에서 , 무엇을 움직일지에 대해서는 둘중 무엇을 움직이는게 더 최소값을 찾는지 정해서 그걸 움직이도록 했습니다. 이 경우 이외의 경우는 없을 거라는 일종의 greedy 기법으로 생각해서 알고리즘을 생각했는데.
계속 6%에서 틀리는 걸 보니, 이렇게 생각한 점이 틀린거 같다고 생각했습니다. 그래서 예외 케이스를 생각해보려는데 생각 나지를 않네요..
어떤 부분이 틀렸는지나, 예외케이스를 알려 주세요 ㅜㅜ
댓글을 작성하려면 로그인해야 합니다.
thereon42 6년 전
세 용액이 0에 가장 수렴하는 값을 찾는 문제요,
알고리즘을 설명해드리자면,
정렬된 배열에 대해서 2개의 값을 가장 작은값, 그다음 작은값, 그리고 한 값을 가장 큰 값을 지정해 놓고 시작합니다.
그렇게 해서 합이 음수냐, 양수냐에 맞춰서 배열 값들을 내리거나 올려서 최소값을 찾는 알고리즘입니다.
여기서 가장 작은 값과 그다음 작은 값에서 , 무엇을 움직일지에 대해서는 둘중 무엇을 움직이는게 더 최소값을 찾는지 정해서 그걸 움직이도록 했습니다. 이 경우 이외의 경우는 없을 거라는 일종의 greedy 기법으로 생각해서 알고리즘을 생각했는데.
계속 6%에서 틀리는 걸 보니, 이렇게 생각한 점이 틀린거 같다고 생각했습니다. 그래서 예외 케이스를 생각해보려는데 생각 나지를 않네요..
어떤 부분이 틀렸는지나, 예외케이스를 알려 주세요 ㅜㅜ