-
[Python] λ°±μ€ - 11399 ATM__Python/__Algorithm 2022. 1. 7. 18:12
λ¬Έμ
https://www.acmicpc.net/problem/11399
πΉ λ¬Έμ
μΈνμνμλ ATMμ΄ 1λλ°μ μλ€. μ§κΈ μ΄ ATMμμ Nλͺ μ μ¬λλ€μ΄ μ€μ μμλ€. μ¬λμ 1λ²λΆν° Nλ²κΉμ§ λ²νΈκ° λ§€κ²¨μ Έ μμΌλ©°, iλ² μ¬λμ΄ λμ μΈμΆνλλ° κ±Έλ¦¬λ μκ°μ PiλΆμ΄λ€.
μ¬λλ€μ΄ μ€μ μλ μμμ λ°λΌμ, λμ μΈμΆνλλ° νμν μκ°μ ν©μ΄ λ¬λΌμ§κ² λλ€. μλ₯Ό λ€μ΄, μ΄ 5λͺ μ΄ μκ³ , P1 = 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λΆμ΄ κ±Έλ¦¬κ² λλ€. μ΄ κ²½μ°μ κ° μ¬λμ΄ λμ μΈμΆνλλ° νμν μκ°μ ν©μ 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+3+6+9+13 = 32λΆμ΄λ€. μ΄ λ°©λ²λ³΄λ€ λ νμν μκ°μ ν©μ μ΅μλ‘ λ§λ€ μλ μλ€.
μ€μ μ μλ μ¬λμ μ Nκ³Ό κ° μ¬λμ΄ λμ μΈμΆνλλ° κ±Έλ¦¬λ μκ° Piκ° μ£Όμ΄μ‘μ λ, κ° μ¬λμ΄ λμ μΈμΆνλλ° νμν μκ°μ ν©μ μ΅μκ°μ ꡬνλ νλ‘κ·Έλ¨μ μμ±νμμ€.
πΉ μ λ ₯
첫째 μ€μ μ¬λμ μ N(1 ≤ N ≤ 1,000)μ΄ μ£Όμ΄μ§λ€. λμ§Έ μ€μλ κ° μ¬λμ΄ λμ μΈμΆνλλ° κ±Έλ¦¬λ μκ° Piκ° μ£Όμ΄μ§λ€. (1 ≤ Pi ≤ 1,000)
πΉ μΆλ ₯
첫째 μ€μ κ° μ¬λμ΄ λμ μΈμΆνλλ° νμν μκ°μ ν©μ μ΅μκ°μ μΆλ ₯νλ€.
νμ΄ λ°©λ²
πΉ νμ μκ³ λ¦¬μ¦(그리λ, Greedy)
πΉ μ λ ¬
πΉ μμμκ°μ΄ κΈ΄ μ¬λμ΄ μ μμμ λ€μ΄μμΌλ©΄, λ€μ μλ μ¬λμ λκΈ°μκ°μ λ κΈΈμ΄μ§λ€. λ°λΌμ μ€λ¦μ°¨μ μ λ ¬ ν, μ μ¬λμ λκΈ°μκ° + μ μ¬λμ μμμκ°μ μμ°¨μ μΌλ‘ λν κ°μ ꡬνλ€.
ꡬν μ½λ
import sys N = int(sys.stdin.readline()) orders = sorted(map(int,sys.stdin.readline().split())) for i in range(1,len(orders)): orders[i] += orders[i-1] print(sum(orders))
μ€ν μ½λ
π‘
728x90'__Python > __Algorithm' μΉ΄ν κ³ λ¦¬μ λ€λ₯Έ κΈ
[Python] λ°±μ€ - 1463 1λ‘λ§λ€κΈ° (0) 2022.01.07 [Python] λ°±μ€ - 2805 λ무 μλ₯΄κΈ° (0) 2022.01.07 [Python] λ°±μ€ - 11279 μ΅λ ν (0) 2022.01.07 [Python] λ°±μ€ - 4948 λ² λ₯΄νΈλ κ³΅μ€ (0) 2022.01.07 [Python] λ°±μ€ - 11286 μ λκ° ν (0) 2022.01.07