[질문] 이 문제 그리디로 어케 품?

[익명(221.163)]

https://www.acmicpc.net/problem/25947

본인 파라매트릭으로 풀었는데 그리디로 어케한 건지 맞은 사람 코드 봐도 이해가 안감

[익명(61.253)]

너가 N개를 사기로 했으면, 가장 싼 N개를 사야 하고 그 중에서 가장 비싼 a개를 할인받아야함. 이걸 모든 N에 대해 투포인터 느낌으로 돌리면 됨

[익명(221.163)]

ㅇㅇ 그것도 가능하겠다. 근데 슬라이딩 윈도우로 훑어서 하는 거 있던데 그게 이해가 안감

[익명(223.39)]

무조건 큰값을 반값하는게 이득->오름차순 정렬후 n개를 사고 나머지 a개를 반값으로 살때 최댓값 이렇게 푸는거지 않음?

[익명(221.163)]

ㄴㄴ 그렇게 간단한 문제가 아님

[익명(223.39)]

? a인덱스 증가시키면서 n개 개수 관리하는 식으로 대회때 맞췄는데?

[익명(221.163)]

내가 잘못 이해했음. 알려줭

[익명(223.39)]

정렬후 처음 k개로 예산넘으면 예산넘기전이 답 아니면 k개를 1~k, 2~k+1 증가시키면서 k개를 제외한 앞부분의 값을 투포인터마냥 예산따라 증가시키면서 관리하며 최댓값 찾기

[익명(221.163)]

ㄱㅅ

[ㅁ(118.218)]

나 이거 직접 시험봐서 맞췃는데 정렬한 다음 b예산 안넘을때까지 사고 산거중에 가장 비싼 선물을 i번이라고 하면 i번 할인 > i+1번 구입 > 구입실패하면 i-1번 할인 > i+1번 구입

[ㅁ(118.218)]

이런식으로 하나할인 다음거 구매 실패하면 전꺼 할인 다시 구매 성공하면 성공한거 할인 다음거 구매 전전꺼 할인 머 대충 이런식으로 풀었음

[익명(221.163)]

아 그렇게 해도 풀리다니 ㄷㄷ

[ㅁ(118.218)]

이거 실버 2박에 안댐? 나 ㅈㄴ 고민해서 푼거였는데 ㅅㅂ.. 물골딱이였네

[익명(221.163)]

개빨리 풀었는데? ㅋㅋㅋㅋㅋ

[ㅁ(118.218)]

솔직히 한 골3 이랬으면 대회끝나고 나름 열심히 했네 했을틴데 실버2 보니까 한숨나옴 ㅋㅋ 공부 더 해야겠네

[린렌(karasuta)]

완전 그리디하게 풀려면 2로 나눠서 정렬조지고 k번째 추가할 때 k-a번째만큼 더하면서 추가하면 되는거아닌가