deo2kim
๋งž์™œํ‹€
deo2kim
์ „์ฒด ๋ฐฉ๋ฌธ์ž
์˜ค๋Š˜
์–ด์ œ
  • ๋ถ„๋ฅ˜ ์ „์ฒด๋ณด๊ธฐ
    • CS
      • Algorithm
      • Data Structure
      • Network
      • DB
      • OS
    • Algorithm Problem
      • Python
      • JavaScript
    • Programming language
      • Python
      • JavaScript
    • Tool
      • Jquery
      • React
    • ๊ฐœ๋ฐœ
    • Infra

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

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

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

์ธ๊ธฐ ๊ธ€

์ตœ๊ทผ ๋Œ“๊ธ€

์ตœ๊ทผ ๊ธ€

ํ‹ฐ์Šคํ† ๋ฆฌ

๋ฐ˜์‘ํ˜•
hELLO ยท Designed By ์ •์ƒ์šฐ.
deo2kim

๋งž์™œํ‹€

[python] ๋ฐฑ์ค€ - 1052. ๋ฌผ๋ณ‘
Algorithm Problem/Python

[python] ๋ฐฑ์ค€ - 1052. ๋ฌผ๋ณ‘

2021. 9. 2. 14:23
๋ฐ˜์‘ํ˜•

๐Ÿค”๋ฌธ์ œ ํ•ด๊ฒฐ

  • S1 | ์ด์ง„๋ฒ•

 

  1. ๋ฌผ์˜ ์–‘์ด 1, 2, 4, 8, 16, ... ์ด๋ ‡๊ฒŒ ์ฆ๊ฐ€ํ•˜๋ฏ€๋กœ ์ด์ง„์ˆ˜์ฒ˜๋Ÿผ ์ƒ๊ฒผ๋‹ค.
  2. ๊ฐ™์€ ์ˆ˜๋ฅผ ๋”ํ•˜๋ฉด ๋‹ค์Œ ์ˆ˜ ํ•˜๋‚˜๊ฐ€ ๋‚˜์˜จ๋‹ค. ์ด์ง„์ˆ˜๋กœ ๋ณด๋ฉด
    1. ex) 100 + 100 = 1000
  3. ์˜ˆ์‹œ๋กœ ์„ค๋ช…ํ•ด๋ณด์ž๋ฉด N = 11 ์ผ ๋•Œ
    1. ๋ฌผ๋ณ‘: 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1
      1. ๋ฌผ๋ณ‘ํ•ฉ: 2, 2, 2, 2, 2, 1
      2. ๋ฌผ๋ณ‘ํ•ฉ: 4, 4, 2, 1
      3. ๋ฌผ๋ณ‘ํ•ฉ: 8, 2, 1
  4. ๋ฌผ๋ณ‘์€ ๊ฒฐ๊ตญ 3๊ฐœ๊ฐ€ ๋œ๋‹ค.
  5. 11์„ ์ด์ง„์ˆ˜๋กœ ๋ฐ”๊พธ๋ฉด 1011 ์ด๋‹ค.
  6. ๊ฒฐ๊ตญ 1์˜ ๊ฐœ์ˆ˜๊ฐ€ ๋‹ค ํ•ฉ์ณค์„ ๋•Œ์˜ ๋ฌผ๋ณ‘์˜ ๊ฐœ์ˆ˜๊ฐ€ ๋œ๋‹ค.
  7. ๊ทธ๋Ÿผ 1์˜ ๊ฐœ์ˆ˜๋ฅผ ์ค„์ด๊ณ  ์‹ถ์œผ๋ฉด ์ด์ง„์ˆ˜ ๋ง์…ˆ์„ ์ด์šฉํ•œ๋‹ค.
    1. 1011(11) + 0001(1) => 1100(12)
    2. 1100(12) + 0100(4) => 10000(16)

๐Ÿš€ ์ด์ง„์ˆ˜๋ฅผ ์ž˜ ์ด์šฉํ•ด์„œ ๋ฌธ์ œ๋ฅผ ํ’€์–ด๋ณด์ž!

1์”ฉ ์ฆ๊ฐ€์‹œ์ผœ๊ฐ€๋ฉด์„œ ํ™•์ธ์„ํ•ด๋„ ํ†ต๊ณผํ•  ์ˆ˜ ์žˆ์ง€๋งŒ ์‹œ๊ฐ„์ฐจ์ด๊ฐ€ ๋งŽ์ด ๋‚œ๋‹ค.

 

๐Ÿ’ป์†Œ์Šค ์ฝ”๋“œ

# ๋ฌธ์ œ ์ ‘๊ทผ๋ฒ•์ด ์ค‘์š”ํ•˜๋‹ค.
# ๋ญ”๊ฐ€ 2์ง„๋ฒ•๊ฐ™์ด ์ƒ๊ฒผ๋‹ค.
# 2์ง„๋ฒ•์œผ๋กœ ํ’€์–ด๋ณด์ž

# N์„ ์ด์ง„๋ฒ•์œผ๋กœ ๋ฐ”๊พธ๋ฉด (ex, 11 => 1011)
# ๋ฌผ๋ณ‘: 1,1,1,1,1,1,1,1,1,1,1
# ํ•ฉ์น˜๊ธฐ: 2,2,2,2,2,1
# ํ•ฉ์น˜๊ธฐ: 4,4,2,1
# ํ•ฉ์น˜๊ธฐ: 8,2,1
# ๋ญ”๊ฐ€ ๊ทœ์น™์ด ๋ณด์ธ๋‹ค.
# ๊ฒฐ๋ก : N์„ ์ด์ง„๋ฒ•์œผ๋กœ ๋ฐ”๊พผ ์ˆ˜์˜ 1์˜ ๊ฐœ์ˆ˜๊ฐ€
# ๋ฌผ์„ ์ตœ๋Œ€๋กœ ํ•ฉ์นœ ํ›„์˜ ๋ฌผ๋ณ‘์˜ ๊ฐœ์ˆ˜์ด๋‹ค.
N, K = map(int, input().split())

purchased_water_bottle_cnt = 0

while bin(N).count('1') > K:
    idx = bin(N)[::-1].index('1')
    purchased_water_bottle_cnt += 2**idx
    N += 2**idx

print(purchased_water_bottle_cnt)

 

๐Ÿ“•๋ฌธ์ œ ํ™•์ธ

์ถœ์ฒ˜: BACKJOON ONLINE JUDGE

๋ฐ˜์‘ํ˜•
์ €์ž‘์žํ‘œ์‹œ ๋น„์˜๋ฆฌ ๋ณ€๊ฒฝ๊ธˆ์ง€ (์ƒˆ์ฐฝ์—ด๋ฆผ)

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

[python] ๋ฐฑ์ค€ - 13023. ABCDE  (0) 2021.09.04
[python] ๋ฐฑ์ค€ - 2615. ์˜ค๋ชฉ  (2) 2021.09.03
[python] ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค - ์ด์ง„ ๋ณ€ํ™˜ ๋ฐ˜๋ณตํ•˜๊ธฐ(์›”๊ฐ„ ์ฝ”๋“œ ์ฑŒ๋ฆฐ์ง€ ์‹œ์ฆŒ1)  (0) 2021.09.01
[python] ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค - ๋‹ค๋‹จ๊ณ„ ์นซ์†” ํŒ๋งค(2021 Dev-Matching: ์›น ๋ฐฑ์—”๋“œ ๊ฐœ๋ฐœ์ž(์ƒ๋ฐ˜๊ธฐ))  (0) 2021.08.23
[python] ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค - ์•ฝ์ˆ˜์˜ ๊ฐœ์ˆ˜์™€ ๋ง์…ˆ  (0) 2021.06.21
    'Algorithm Problem/Python' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€
    • [python] ๋ฐฑ์ค€ - 13023. ABCDE
    • [python] ๋ฐฑ์ค€ - 2615. ์˜ค๋ชฉ
    • [python] ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค - ์ด์ง„ ๋ณ€ํ™˜ ๋ฐ˜๋ณตํ•˜๊ธฐ(์›”๊ฐ„ ์ฝ”๋“œ ์ฑŒ๋ฆฐ์ง€ ์‹œ์ฆŒ1)
    • [python] ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค - ๋‹ค๋‹จ๊ณ„ ์นซ์†” ํŒ๋งค(2021 Dev-Matching: ์›น ๋ฐฑ์—”๋“œ ๊ฐœ๋ฐœ์ž(์ƒ๋ฐ˜๊ธฐ))
    deo2kim
    deo2kim
    ์ฝ”๋”ฉ ๊ธฐ๋กํ•˜๊ธฐ

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