Algorithm/BOJ

๋ฐฑ์ค€(BOJ) 11047๋ฒˆ ๋™์ „ 0 [๊ทธ๋ฆฌ๋””(Greedy)/์•Œ๊ณ ๋ฆฌ์ฆ˜/ํŒŒ์ด์ฌ(python)]

2021. 8. 11. 16:51
๋ชฉ์ฐจ
  1. ๊ทธ๋ฆฌ๋”” ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋ž€?
  2.  
  3.  
  4. ๋ฌธ์ œ
  5. ์ž…๋ ฅ
  6. ์ถœ๋ ฅ
  7. โœ ์˜ˆ์ œ ์„ค๋ช…
  8.  
  9. ๐Ÿ‘‰ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์„ค๋ช…
  10. ๐Ÿ“ ์ฝ”๋“œ

๊ทธ๋ฆฌ๋”” ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋ž€?

"๋งค ์„ ํƒ์—์„œ ์ง€๊ธˆ ์ด ์ˆœ๊ฐ„ ๋‹น์žฅ ์ตœ์ ์ธ ๋‹ต์„ ์„ ํƒํ•˜์—ฌ ์ ํ•ฉํ•œ ๊ฒฐ๊ณผ๋ฅผ ๋„์ถœํ•˜์ž"๋ผ๋Š” ๋ชจํ† ๋ฅผ ๊ฐ€์ง€๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์„ค๊ณ„ ๊ธฐ๋ฒ•์ด๋‹ค.

 

๊ฑฐ์Šค๋ฆ„๋ˆ์„ ๋Œ๋ ค์ฃผ๋Š” ๋ฌธ์ œ๋ฅผ ์ƒ๊ฐํ•ด๋ณด์ž.

์šฐ๋ฆฌ๋Š” ๋Œ€๋ถ€๋ถ„ ๊ฑฐ์Šค๋ฆ„๋ˆ์„ ๋Œ๋ ค์ค„๋•Œ ํฐ ๋‹จ์œ„์˜ ๋™์ „๋ถ€ํ„ฐ ๊ฑฐ์Šฌ๋Ÿฌ์ค€๋‹ค.

ex ) 500์›์„ ๋Œ๋ ค์ค˜์•ผ ํ•œ๋‹ค๋ฉด, 100์›์„ 5๊ฐœ ์ฃผ๋Š” ๊ฒƒ๋ณด๋‹ค 500์›์„ 1๊ฐœ ์ฃผ๋Š” ํŽธ์ด ๋” ํŽธํ•˜๋‹ค.

 

ํ•˜์ง€๋งŒ ๋งŒ์•ฝ์— ๋™์ „์˜ ๋‹จ์œ„๊ฐ€ 100, 250, 300 ์ด๋ผ๋ฉด, (300 * 1) + (100 * 2) ๋กœ 3๊ฐœ๋กœ ๊ฑฐ์Šฌ๋Ÿฌ์ฃผ๋Š” ๊ฒƒ๋ณด๋‹ค๋Š” 250 * 2 ์˜ ๋ฐฉ๋ฒ•์œผ๋กœ 2๊ฐœ๋กœ ๊ฑฐ์Šฌ๋Ÿฌ์ฃผ๋Š” ๊ฒƒ์ด ๋” ์ตœ์ ์˜ ๋ฐฉ๋ฒ•์ด๋‹ค.

 

๋”ฐ๋ผ์„œ ๊ทธ๋ฆฌ๋”” ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ํ•ญ์ƒ ์ตœ์ ์˜ ํ•ด๋ฅผ ์ œ๊ณตํ•ด์ฃผ๋Š” ๊ฒƒ์€ ์•„๋‹ˆ๋‹ค.

ํ•˜์ง€๋งŒ ๋งŒ์•ฝ ์ด ์ƒํ™ฉ์—์„œ ํฐ ๋‹จ์œ„์˜ ์ˆ˜๋ถ€ํ„ฐ ๊ฑฐ์Šฌ๋Ÿฌ์ค˜์•ผํ•˜๋Š” ์กฐ๊ฑด์ด ์กด์žฌํ•  ๋•Œ ๊ทธ๋ฆฌ๋”” ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด ์ตœ์ ์˜ ํ•ด๋ฅผ ์ œ๊ณตํ•ด ์ค„ ์ˆ˜ ์žˆ๋‹ค.

 


 

 

11047๋ฒˆ: ๋™์ „ 0

์ฒซ์งธ ์ค„์— N๊ณผ K๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. (1 โ‰ค N โ‰ค 10, 1 โ‰ค K โ‰ค 100,000,000) ๋‘˜์งธ ์ค„๋ถ€ํ„ฐ N๊ฐœ์˜ ์ค„์— ๋™์ „์˜ ๊ฐ€์น˜ Ai๊ฐ€ ์˜ค๋ฆ„์ฐจ์ˆœ์œผ๋กœ ์ฃผ์–ด์ง„๋‹ค. (1 โ‰ค Ai โ‰ค 1,000,000, A1 = 1, i โ‰ฅ 2์ธ ๊ฒฝ์šฐ์— Ai๋Š” Ai-1์˜ ๋ฐฐ์ˆ˜)

www.acmicpc.net

 

๋ฌธ์ œ

์ค€๊ทœ๊ฐ€ ๊ฐ€์ง€๊ณ  ์žˆ๋Š” ๋™์ „์€ ์ด N์ข…๋ฅ˜์ด๊ณ , ๊ฐ๊ฐ์˜ ๋™์ „์„ ๋งค์šฐ ๋งŽ์ด ๊ฐ€์ง€๊ณ  ์žˆ๋‹ค.

๋™์ „์„ ์ ์ ˆํžˆ ์‚ฌ์šฉํ•ด์„œ ๊ทธ ๊ฐ€์น˜์˜ ํ•ฉ์„ K๋กœ ๋งŒ๋“ค๋ ค๊ณ  ํ•œ๋‹ค. ์ด๋•Œ ํ•„์š”ํ•œ ๋™์ „ ๊ฐœ์ˆ˜์˜ ์ตœ์†Ÿ๊ฐ’์„ ๊ตฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค.

์ž…๋ ฅ

์ฒซ์งธ ์ค„์— N๊ณผ K๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. (1 โ‰ค N โ‰ค 10, 1 โ‰ค K โ‰ค 100,000,000)

๋‘˜์งธ ์ค„๋ถ€ํ„ฐ N๊ฐœ์˜ ์ค„์— ๋™์ „์˜ ๊ฐ€์น˜ Ai๊ฐ€ ์˜ค๋ฆ„์ฐจ์ˆœ์œผ๋กœ ์ฃผ์–ด์ง„๋‹ค. (1 โ‰ค Ai โ‰ค 1,000,000, A1 = 1, i โ‰ฅ 2์ธ ๊ฒฝ์šฐ์— Ai๋Š” Ai-1์˜ ๋ฐฐ์ˆ˜)

์ถœ๋ ฅ

์ฒซ์งธ ์ค„์— K์›์„ ๋งŒ๋“œ๋Š”๋ฐ ํ•„์š”ํ•œ ๋™์ „ ๊ฐœ์ˆ˜์˜ ์ตœ์†Ÿ๊ฐ’์„ ์ถœ๋ ฅํ•œ๋‹ค.

 

 

โœ ์˜ˆ์ œ ์„ค๋ช…

์ด 10๊ฐœ์˜ ๋™์ „ ๋‹จ์œ„๊ฐ€ ์ฃผ์–ด์ง€๊ณ , 4200์›์„ ๊ฑฐ์Šฌ๋Ÿฌ์ค˜์•ผํ•  ๋•Œ ํ•„์š”ํ•œ ์ตœ์†Œ์˜ ๋™์ „ ๊ฐœ์ˆ˜๋Š”?

( 1000 * 4 ) + ( 100 * 2 ) -> ์ด 6๊ฐœ ์ด๋‹ค.

 

๐Ÿ‘‰ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์„ค๋ช…

ํฐ ์ˆ˜๋ถ€ํ„ฐ k๊ฐ’๊ณผ ๋น„๊ตํ•œ๋‹ค.

๋งŒ์•ฝ ๋™์ „์˜ ๋‹จ์œ„๊ฐ€ k ๋ณด๋‹ค ์ž‘๋‹ค๋ฉด k๋ฅผ ๋‹จ์œ„๊ฐ’์œผ๋กœ ๋‚˜๋ˆˆ ๋ชซ์˜ ์ˆซ์ž๋ฅผ count์— ์ถ”๊ฐ€ํ•œ๋‹ค.

k๊ฐ’์€ ๊ทธ ๋™์ „์˜ ๋‹จ์œ„๋กœ ๋‚˜๋ˆˆ ๋‚˜๋จธ์ง€ ๊ฐ’์œผ๋กœ ๋ณ€๊ฒฝํ•œ๋‹ค.

๋ฐ˜๋ณตํ•˜๊ณ , k๊ฐ’์ด 0์ด ๋˜๋ฉด count๊ฐ’์„ return ํ•œ๋‹ค.

 

๐Ÿ“ ์ฝ”๋“œ

import sys

def count_coin(L, k):
    count = 0
    for i in range(len(L)):
        if k == 0: break
        com = L.pop()
        if com <= k:
            count += k//com
            k %= com
    return count

N, K = map(int, sys.stdin.readline().split())
L = [int(sys.stdin.readline()) for i in range(N)]

print(count_coin(L,K))

 

์ €์ž‘์žํ‘œ์‹œ (์ƒˆ์ฐฝ์—ด๋ฆผ)

'Algorithm > BOJ' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€

๋ฐฑ์ค€(BOJ) 1931๋ฒˆ ํšŒ์˜์‹ค๋ฐฐ์ • [๊ทธ๋ฆฌ๋””(Greedy)/์•Œ๊ณ ๋ฆฌ์ฆ˜/ํŒŒ์ด์ฌ(python)]  (0) 2021.08.07
๋ฐฑ์ค€(BOJ) 11000๋ฒˆ ๊ฐ•์˜์‹ค๋ฐฐ์ • [๊ทธ๋ฆฌ๋””(Greedy)/์•Œ๊ณ ๋ฆฌ์ฆ˜/ํŒŒ์ด์ฌ(python)/ํ]  (0) 2021.08.06
๋ฐฑ์ค€(BOJ) 1158๋ฒˆ ์š”์„ธํ‘ธ์Šค [์•Œ๊ณ ๋ฆฌ์ฆ˜/ํŒŒ์ด์ฌ(python)/์—ฐ๊ฒฐ๋ฆฌ์ŠคํŠธ]  (0) 2021.07.07
๋ฐฑ์ค€(BOJ) 9012๋ฒˆ ์Šคํƒ๋ฌธ์ œ [ํŒŒ์ด์ฌ(python)]  (0) 2021.07.02
๋ฐฑ์ค€(BOJ) 10828๋ฒˆ ์Šคํƒ๋ฌธ์ œ [ํŒŒ์ด์ฌ(python) / ์‹œ๊ฐ„์ดˆ๊ณผ ์—๋Ÿฌ]  (0) 2021.06.28
  1. ๊ทธ๋ฆฌ๋”” ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋ž€?
  2.  
  3.  
  4. ๋ฌธ์ œ
  5. ์ž…๋ ฅ
  6. ์ถœ๋ ฅ
  7. โœ ์˜ˆ์ œ ์„ค๋ช…
  8.  
  9. ๐Ÿ‘‰ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์„ค๋ช…
  10. ๐Ÿ“ ์ฝ”๋“œ
'Algorithm/BOJ' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€
  • ๋ฐฑ์ค€(BOJ) 1931๋ฒˆ ํšŒ์˜์‹ค๋ฐฐ์ • [๊ทธ๋ฆฌ๋””(Greedy)/์•Œ๊ณ ๋ฆฌ์ฆ˜/ํŒŒ์ด์ฌ(python)]
  • ๋ฐฑ์ค€(BOJ) 11000๋ฒˆ ๊ฐ•์˜์‹ค๋ฐฐ์ • [๊ทธ๋ฆฌ๋””(Greedy)/์•Œ๊ณ ๋ฆฌ์ฆ˜/ํŒŒ์ด์ฌ(python)/ํ]
  • ๋ฐฑ์ค€(BOJ) 1158๋ฒˆ ์š”์„ธํ‘ธ์Šค [์•Œ๊ณ ๋ฆฌ์ฆ˜/ํŒŒ์ด์ฌ(python)/์—ฐ๊ฒฐ๋ฆฌ์ŠคํŠธ]
  • ๋ฐฑ์ค€(BOJ) 9012๋ฒˆ ์Šคํƒ๋ฌธ์ œ [ํŒŒ์ด์ฌ(python)]
DAHLIA CHOI
DAHLIA CHOI
DAHLIA CHOI
๐ŸŒผ dali's log ๐ŸŒผ
DAHLIA CHOI
์ „์ฒด
์˜ค๋Š˜
์–ด์ œ
  • ๋ถ„๋ฅ˜ ์ „์ฒด๋ณด๊ธฐ (103)
    • Spring (42)
    • JAVA & OOP (8)
    • AWS (2)
    • DevOps (5)
    • Network (7)
    • DB (5)
    • Algorithm (9)
      • BOJ (6)
      • PROGRAMMERS (2)
      • LEETCODE (0)
    • Books (5)
    • ํŠธ๋Ÿฌ๋ธ” ์ŠˆํŒ… (5)
    • ํšŒ๊ณ  (0)
    • ๊ธฐํƒ€ (5)
    • FRENCH (1)
    • ํ•„์‚ฌ (2)
    • ๊ฒฝํ—˜ (5)

๋ธ”๋กœ๊ทธ ๋ฉ”๋‰ด

  • ํ™ˆ
  • ํƒœ๊ทธ
  • ๋ฐฉ๋ช…๋ก

๊ณต์ง€์‚ฌํ•ญ

์ธ๊ธฐ ๊ธ€

์ตœ๊ทผ ๊ธ€

hELLO ยท Designed By ์ •์ƒ์šฐ.
DAHLIA CHOI
๋ฐฑ์ค€(BOJ) 11047๋ฒˆ ๋™์ „ 0 [๊ทธ๋ฆฌ๋””(Greedy)/์•Œ๊ณ ๋ฆฌ์ฆ˜/ํŒŒ์ด์ฌ(python)]
์ƒ๋‹จ์œผ๋กœ

ํ‹ฐ์Šคํ† ๋ฆฌํˆด๋ฐ”

๋‹จ์ถ•ํ‚ค

๋‚ด ๋ธ”๋กœ๊ทธ

๋‚ด ๋ธ”๋กœ๊ทธ - ๊ด€๋ฆฌ์ž ํ™ˆ ์ „ํ™˜
Q
Q
์ƒˆ ๊ธ€ ์“ฐ๊ธฐ
W
W

๋ธ”๋กœ๊ทธ ๊ฒŒ์‹œ๊ธ€

๊ธ€ ์ˆ˜์ • (๊ถŒํ•œ ์žˆ๋Š” ๊ฒฝ์šฐ)
E
E
๋Œ“๊ธ€ ์˜์—ญ์œผ๋กœ ์ด๋™
C
C

๋ชจ๋“  ์˜์—ญ

์ด ํŽ˜์ด์ง€์˜ URL ๋ณต์‚ฌ
S
S
๋งจ ์œ„๋กœ ์ด๋™
T
T
ํ‹ฐ์Šคํ† ๋ฆฌ ํ™ˆ ์ด๋™
H
H
๋‹จ์ถ•ํ‚ค ์•ˆ๋‚ด
Shift + /
โ‡ง + /

* ๋‹จ์ถ•ํ‚ค๋Š” ํ•œ๊ธ€/์˜๋ฌธ ๋Œ€์†Œ๋ฌธ์ž๋กœ ์ด์šฉ ๊ฐ€๋Šฅํ•˜๋ฉฐ, ํ‹ฐ์Šคํ† ๋ฆฌ ๊ธฐ๋ณธ ๋„๋ฉ”์ธ์—์„œ๋งŒ ๋™์ž‘ํ•ฉ๋‹ˆ๋‹ค.