12234번 - Data Packing (Small)
안녕하세요, 읽어주셔서 감사합니다.이 문제를 풀기 위한 제 아이디어는 이렇습니다.
투 포인터 알고리즘을 사용할 것이고, _left = 0, _right = N-1 인덱스를 지정합니다.
루프하면서 _arr[_left] + _arr[_right] 가 모두 한 디스크에 들어갈 수 있는 상황이라면, _left 를 증가시켜 인덱스를 이동하고,
그렇지 않는다면 _right에 해당하는 파일이 디스크 1개를 차지한다는 것으로 가정하여, _right는 계속해서 감소시킵니다.
그런 상황에서 디스크 1개씩은 루프마다 필연적으로 사용하게 되니 증가하도록 합니다.
이후에 출력을 하면 예제들은 다 패스하는데, 50%에서 틀렸다고 나와 답을 알 수 없는 상황이 되어버립니다.
혹시 반례를 아신다면 공유 한번 부탁드립니다.
감사합니다.
자문 자답입니다
정렬이 된 배열을 주는게 아니었습니다.
정렬 후에 로직 돌리면 풀립니다.
댓글을 작성하려면 로그인해야 합니다.
sin15348 1년 전
안녕하세요, 읽어주셔서 감사합니다.
이 문제를 풀기 위한 제 아이디어는 이렇습니다.
투 포인터 알고리즘을 사용할 것이고, _left = 0, _right = N-1 인덱스를 지정합니다.
루프하면서 _arr[_left] + _arr[_right] 가 모두 한 디스크에 들어갈 수 있는 상황이라면, _left 를 증가시켜 인덱스를 이동하고,
그렇지 않는다면 _right에 해당하는 파일이 디스크 1개를 차지한다는 것으로 가정하여, _right는 계속해서 감소시킵니다.
그런 상황에서 디스크 1개씩은 루프마다 필연적으로 사용하게 되니 증가하도록 합니다.
이후에 출력을 하면 예제들은 다 패스하는데, 50%에서 틀렸다고 나와 답을 알 수 없는 상황이 되어버립니다.
혹시 반례를 아신다면 공유 한번 부탁드립니다.
감사합니다.