白駿「ATM(11399号)」
問題リンクと問題内容
https://www.acmicpc.net/problem/11399
質問する
仁河銀行にはATMが1台しかありません.今このATMの前にN人が並んでいます.人の番号は1番からN番まで、i番です. 人がお金を引き出すのにかかる時間はPi分です.
人々が並んでいる順番によって、お金を引き出すのにかかる時間の和が違います.例えば、全部で5人、P 1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2人のことを考えてみよう[1.2.3.4.5]順番に並んでいれば、1番の人は3分以内にお金を引き出すことができます.2番の人は1番の人がお金を引くまで待たなければならないので、3+1=4分です.3番の人は1番2番の人がお金を引き出すまで3+1+4=8分かかります.4番は3+1+4+3=11分、5番は3+1+4+3+2=13分です.この場合、1人当たりの引き出しに要する時間の合計は、3+4+8+11+13=39分である.
[2,5,1,4,3]順に並び、2番が1分、5番が1+2=3分、1番が1+2+3=6分、4番が1+2+3+3=9分、3番が1+2+3+3+4=13分です.1人当たりの引き出しに要する時間の合計は1+3+6+9+13=32分です.この方法よりも必要な時間の和を最小限に抑えることはできない.
並んでいる人数Nと一人当たりの引き出しに要する時間Piを指定する場合は、一人当たりの引き出しに要する時間のプロトコルの最大値を求めるプログラムを作成してください.
入力
1行目は人数N(1≦N≦1000)を与える.2行目は一人一人がお金を引き出すのに必要な時間Piを与えます.(1 ≤ Pi ≤ 1,000)
しゅつりょく
最初の行 引き出しに要する時間のプロトコルの最大値を1人あたり印刷します.
入力例1問題作成者: baekjoon 件のエラーを見つけた人: hakgb11 プールコード
https://www.acmicpc.net/problem/11399
質問する
仁河銀行にはATMが1台しかありません.今このATMの前にN人が並んでいます.人の番号は1番からN番まで、i番です. 人がお金を引き出すのにかかる時間はPi分です.
人々が並んでいる順番によって、お金を引き出すのにかかる時間の和が違います.例えば、全部で5人、P 1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2人のことを考えてみよう[1.2.3.4.5]順番に並んでいれば、1番の人は3分以内にお金を引き出すことができます.2番の人は1番の人がお金を引くまで待たなければならないので、3+1=4分です.3番の人は1番2番の人がお金を引き出すまで3+1+4=8分かかります.4番は3+1+4+3=11分、5番は3+1+4+3+2=13分です.この場合、1人当たりの引き出しに要する時間の合計は、3+4+8+11+13=39分である.
[2,5,1,4,3]順に並び、2番が1分、5番が1+2=3分、1番が1+2+3=6分、4番が1+2+3+3=9分、3番が1+2+3+3+4=13分です.1人当たりの引き出しに要する時間の合計は1+3+6+9+13=32分です.この方法よりも必要な時間の和を最小限に抑えることはできない.
並んでいる人数Nと一人当たりの引き出しに要する時間Piを指定する場合は、一人当たりの引き出しに要する時間のプロトコルの最大値を求めるプログラムを作成してください.
入力
1行目は人数N(1≦N≦1000)を与える.2行目は一人一人がお金を引き出すのに必要な時間Piを与えます.(1 ≤ Pi ≤ 1,000)
しゅつりょく
最初の行 引き出しに要する時間のプロトコルの最大値を1人あたり印刷します.
入力例1
5
3 1 4 3 2
サンプル出力132
ソース# 백준 11399번 'ATM' 그리디
# 결과값 변수
result = 0
# 저장할 변수
save = 0
# 사람 수 입력
N = int(input())
time = list(map(int, input().split()))
# 시간 리스트 정렬
# 리스트의 값이 오름차순이 되어야 시간의 합을 최소로 할수 있다.
# 3 1 4 3 2 의 시간의 합은 : 3 + 4(3+1) + 8(3+1+4) + 11(3+1+4+3) + 13(3+1+4+3+2) = 39분
# 오름차순으로 정렬해 1 2 3 3 4 의 시간의 합은 1 + 3(1+2) + 6(1+2+3) + 9(1+2+3+3) + 13(1+2+3+3+4) = 32분
time.sort()
# 반복을 통해 결과값 도출
for times in time:
save += times
result += save
print(result)
しゅつりょくinput :
5
3 1 4 3 2
output :
32
Reference
この問題について(白駿「ATM(11399号)」), 我々は、より多くの情報をここで見つけました https://velog.io/@chobae/백준-ATM11399번テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol