11052번 - 카드 구매하기
내림차순의 우선순위큐에 넣고 이득/카드개수를 해서 큰 순서대로 나와서 뺴게 하는 알고리즘인데요, 예제는 모두 잘 되는데
10%에서 틀렸습니다가 뜹니다. 왜일까요? 나누면 짤리는 부분 감안하여 double로 하고, 또 round까지 써주었는데 말이죠, 답변부탁드립니다.
class이름은 Main 으로 하였고, 10%에서 틀렸다고뜹니다...
10
1 100 160 1 1 1 1 1 1 1
이게 반례인데
정답은 520이고
출력결과는 481나오네요
우선순위로 집어넣어주신건 50이랑 53.333.....이지만요
아... greedy가 성립이 안되는 문제였군요 댓글정말감사합니다!!
이 문제는 1차원 DP 문제 입니다. 아래 문제 풀이 참고하세요.
댓글을 작성하려면 로그인해야 합니다.
ks8686 4년 전
내림차순의 우선순위큐에 넣고 이득/카드개수를 해서 큰 순서대로 나와서 뺴게 하는 알고리즘인데요, 예제는 모두 잘 되는데
10%에서 틀렸습니다가 뜹니다. 왜일까요? 나누면 짤리는 부분 감안하여 double로 하고, 또 round까지 써주었는데 말이죠, 답변부탁드립니다.