N개의 계좌가 있다 하고
각각의 계좌는 i만큼 의 금액을 입금할 수 있다고 함
이 계좌들에 돈을 입금할건데
얼만큼 입금할건지는 이제 이 프로그램의 사용자가 입력(N이랑 i도 입력받음)
단 사용자가 입력하는 금액은 a, b, c, ..., 형식으로 주어지는데 입금의 편의를 위해 각 금액은 쪼개질 수 없음.
프로그램은 이 돈들을 각 계좌에 넘치지 않게 담아야함.
이걸 수행하는 알고리즘을 짜보시오.
각각의 계좌는 i만큼 의 금액을 입금할 수 있다고 함
이 계좌들에 돈을 입금할건데
얼만큼 입금할건지는 이제 이 프로그램의 사용자가 입력(N이랑 i도 입력받음)
단 사용자가 입력하는 금액은 a, b, c, ..., 형식으로 주어지는데 입금의 편의를 위해 각 금액은 쪼개질 수 없음.
프로그램은 이 돈들을 각 계좌에 넘치지 않게 담아야함.
이걸 수행하는 알고리즘을 짜보시오.
백팩문제자늠
그냥 백팩문제가아닌데
하튼 풀어나봐라
흐미~짱어렵
글이 바꼈네
계좌를 가방으로써서 오타만 수정한거
얼만큼->얼마큼 (국어사전 - 얼마큼 :얼마만큼이 줄어든 말.) [리듬 맞춤법 봇♬]
계좌를 큰것순으로 정렬하고, 입금을 큰것순으로 정렬해서 큰것을 넣어서 넘지 않은선까지 작은것까지 꾸겨넣는거야 , 다은 큰것에다가, 나머지중에서 큰것을 넣어서 넘지 않느선까지 작은건가지 꾸겨넣는겨..
계좌는 다 똑같은 크기
그럼 한 계좌에 가장큰돈부터 꾸겨넣어, 남는공간에 다음큰것이 들어갈 수 있으면 꾸겨넣고, 끝까지 다 확인해서 더이상 못넣으면 다음 계좌 반복...
ㄴ 단순히 큰거먼저집어넣는 문제는 아닌거같은게
이문제는 입력된 금액들의 총합이 계좌들의 크기 총합을 넘을수도있으니 그걸 고려해서풀어야함 그럴경우 당연히 가장 입금을 많이할수있는 답을 줘야하고
데
그리디안댐
계좌가 한개있고 계좌크기가 700이라할때 돈이 500 400 300 들어오면 란씨맨얘기대로는 안풀린다
왜 안풀리냐 500넣고 다음계좌에 400,300 들어가는데
계좌크기가 700하나인데 어떻게되냐 ㅋㅋㅋ
계좌가 N 개라며, 다 넣을라면 계좌총액이>입금총액보다 커야되는 조건이 위배되잖아
ㄴN개는 임의의 무한하지않은 수고 입금총액이 계좌총액보다 클수있음. 그땐 최대한 많이쑤셔넣어야함
N+a 개를 임의로 만들어다 다 쑤셔넣어서, N 개의 계좌랑 + a 개의 계좌랑 큰것을 선택해서 교환하면 되게네
??? 아니 모든경우에 대응해야하는데 유저가 N을 작게넣으면 어쩔거냐니깐 N*i가 총액을 담을수없을만큼 작다고할때
니는 걍 문제를 이해못한거임
입금금액을 정렬해서, 임금금액이 계좌보다 큰것을 제외하고, 계좌 1에다가 가장큰 금액을 넣고, 남는공간에다가 넣을 수있을만큼 계속 넣어가는거야. 다 쑤셔들어 갈때까지, 그런다음에 2번 계좌에다가 나머지 입금해야할 액수를 큰것부터 또 넣어, 그래서 다 들어갈때까지 카운팅을하고, 이 계좌를 다시 정렬해서 N 번까지 출력하면 되잖아
ㄴ야임마 이거 짐을 못쪼개는 배낭채우기 문제를 기반으로한거같은데 그럼 그리디로 안풀려
401 입금하고 400+399 입금하고 398+397 입금해서.... 다 넣고, 큰것부터 정렬해서 N 번째까지 출력하면 최대치지..
안쪼개진다는데뭔 399같은소리야
ㄴ 뭘 쪼갰다고 그래, 안쪼갰는데...