USACO January 2012 Bronze Division
문제: https://www.acmicpc.net/problem/5911
풀이: https://shnoh171.github.io/competitive%20programming/2019/01/02/gifts.html
정렬 O(N lg N) 이후, 그리디 알고리즘 적용해서 O(N)에 풀릴 문제를 N = 1000으로 제한하고, "어떻게든 풀리지? 난이도 Bronze야" 하는 게 올바른 출제 방향인지는 모르겠다.
어쨌든 쉬운 그리디 알고리즘을 약간 변형한 문제니 풀어보자.
아무리봐도 정렬해야 하는데 어떻게 N으로 풀지 오지네 - dc App
아 정렬해야 하네 미안해 ㅡ.ㅡ
정렬해놓고 인지부조화 왔네
정렬 돼 있으면 n으로 풀리긴하징 - dc App
어쨌든 input size 제한을 1000으로 두는건 이상한 것 같어
범위가 커지면 퀵소트 스택터져서 그럴껄 - dc App
차라리 p와 s범위가 작으면 카운팅 솔트로 전체시간 n안에 풀리긴 할듯 - dc App
이건 걍 브론즈 맞는데
정렬 n^2 으로 해도 뚫리라고 범위 이렇게 준듯
풀이 맞나? 0~i까지 합계가 M보다 작거나 같으면 i를 증가시키고 아니면 마지막에 이분탐색 1번 돌려서 확인하면 되네요.
M이 아니라 B를 이야기하는 것 같으니 그것까지는 풀이와 똑같고, 마지막에 왜 이분 탐색을 돌리죠?
일단 i를 최대한 올리고 그 다음에 남는 금액으로 나머지 물품들중에 할인적용해서 보낼수 있는거를 찾는 과정이에요
네 B맞아여
P(i)/2 + S(i) 기준으로 정렬된 리스트가 추가로 있으면 이분 탐색이 가능하겠네유. ㄳㄳ 풀이는 P(i) + S(i) 기준으로 정렬된 리스트만 있다고 생각하고 적은거에유.
저 풀이 반례 있을 것 같은데 아닌가
해당 댓글은 삭제되었습니다.
그렇네요 반례있네
반례 찾음. 2 1506 1000 2 4 1000가 입력일 때 정답은 2인데 1을 출력하네.
헐 처음 정렬할 때 P(i)+S(i)가 동일할 때 P(i)를 기준으로 정렬하면 해결되려나
일단 백준에 신고해야징
아 그걸로는 해결이 안되는구나
1부터 N까지 다 뒤져야겠네
그리디는 아니고 정렬 O(nlgn) 이후 O(n) 하는 간단한 풀이 있네
재채점했습니다.
https://www.acmicpc.net/rejudge/status/all/2250