[๋ฐฑ์ค] 1094 ๋ง๋๊ธฐ with Python
๐ BOJ 1094 ๋ง๋๊ธฐ
๐ก ์กฐ๊ฑด
64cm์ธ ๋ง๋๋ฅผ ๊ฐ์ง๊ณ ์๋ค.
์ง๋ฏผ์ด๋ ์๋ ๊ฐ์ง๊ณ ์๋ ๋ง๋๋ฅผ ๋ ์์ ๋ง๋๋ก ์๋ฅธ๋ค์์, ํ๋ก ๋ถ์ฌ์ ๊ธธ์ด๊ฐ Xcm์ธ ๋ง๋๋ฅผ ๋ง๋ค๋ ค๊ณ ํ๋ค.์๋๋ ๋ง๋๋ฅผ ์๋ฅด๋ ๋ฐฉ๋ฒ์ด๋ค.
1) ์ง๋ฏผ์ด๊ฐ ๊ฐ์ง๊ณ ์๋ ๋ง๋์ ๊ธธ์ด๋ฅผ ๋ชจ๋ ๋ํ๋ค.
์ฒ์์๋ 64cm ๋ง๋ ํ๋๋ง ๊ฐ์ง๊ณ ์๋ค. ์ด๋, ํฉ์ด X๋ณด๋ค ํฌ๋ค๋ฉด, ์๋์ ๊ฐ์ ๊ณผ์ ์ ๋ฐ๋ณตํ๋ค.
1-1) ๊ฐ์ง๊ณ ์๋ ๋ง๋ ์ค ๊ธธ์ด๊ฐ ๊ฐ์ฅ ์งง์ ๊ฒ์ ์ ๋ฐ์ผ๋ก ์๋ฅธ๋ค.
1-2) ๋ง์ฝ, ์์์ ์๋ฅธ ๋ง๋์ ์ ๋ฐ ์ค ํ๋๋ฅผ ๋ฒ๋ฆฌ๊ณ ๋จ์์๋ ๋ง๋์ ๊ธธ์ด์ ํฉ์ด X๋ณด๋ค ํฌ๊ฑฐ๋ ๊ฐ๋ค๋ฉด,์์์ ์๋ฅธ ๋ง๋์ ์ ๋ฐ ์ค ํ๋๋ฅผ ๋ฒ๋ฆฐ๋ค.
2) ์ด์ , ๋จ์์๋ ๋ชจ๋ ๋ง๋๋ฅผ ํ๋ก ๋ถ์ฌ์ Xcm๋ฅผ ๋ง๋ ๋ค.
X๋ 64๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ์์ฐ์
DFS, ์ํ, ๋นํธ๋ง์คํน ์ ํ์ ๋ฌธ์
๐ฅ ์์ค ์ฝ๋
from sys import stdin, setrecursionlimit
import heapq
setrecursionlimit(10 ** 6)
x = int(stdin.readline())
res = 0
sticks = [64]
def solve(sticks):
global res
val = sum(sticks)
if val > x:
temp = heapq.heappop(sticks)
heapq.heappush(sticks, temp // 2)
heapq.heappush(sticks, temp // 2)
if sum(sticks) - (temp // 2) >= x:
heapq.heappop(sticks)
solve(sticks)
elif sum(sticks) >= x:
solve(sticks)
solve(sticks)
print(len(sticks))
๐ ์์ ๋ฐ ์คํ๊ฒฐ๊ณผ
์์
23
์คํ๊ฒฐ๊ณผ
4
โจ๏ธ ๋ฌธ์ ํ์ด
DFS ์๊ณ ๋ฆฌ์ฆ์ ์ฌ์ฉํด์ ํ์ดํ๋ค.
๊ฒฐ๊ณผ๊ฐ์ ์ ์ฅํ res ๋ณ์์ ๋ถ๋ฆฌ๋์ง ์์ ๋ง๋๊ธฐ 64๊ฐ ๋ค์ด๊ฐ์๋ sticks ๋ฆฌ์คํธ๋ฅผ ์์ฑํ๋ค.
solve() ํจ์์ ๋ก์ง์ ์๋์ ๊ฐ์ต๋๋ค.
sticks ๋ฆฌ์คํธ์ ํฉ์ด ์ ๋ ฅ๋ฐ์ ๊ฐ x ๋ณด๋ค ํด ๊ฒฝ์ฐ,
sticks ์์ heapq.heappop() ํจ์๋ฅผ ํตํด ๊ฐ์ฅ ์์ ๊ฐ์ ๋นผ๋ธ๋ค.
๋นผ๋ธ ๊ฐ์ 2๋ก ๋๋ ๋ชซ์ ๋ค์ heapq.heappush()๋ก ๋ค์ ๋ฃ์ด์ค๋ค.๋ง์ฝ, sticks ๋ฆฌ์คํธ์ ํฉ์์ heapq.heappop() ํจ์๋ฅผ ํตํด ๊ฐ์ฅ ์์ ๊ฐ์ ๋บ ๊ฐ์ด x๋ณด๋ค ํฌ๊ฑฐ๋ ๊ฐ๋ค๋ฉด
heapq.heappop() ํจ์๋ฅผ ํตํด ๊ฐ์ฅ ์์ ๊ฐ์ ๋นผ๋ธ๋ค.
solve() ํจ์๋ฅผ ์ฌ๊ทํธ์ถํ๋ค.์์ ์กฐ๊ฑด์ ํด๋นํ์ง ์๊ณ , sticks์ ๋ฆฌ์คํธ์ ํฉ์ด x๋ณด๋ค ํฌ๊ฑฐ๋ ๊ฐ๋ค๋ฉด ๋ค์ solve() ํจ์๋ฅผ ์ฌ๊ทํธ์ถํ๋ค.
sticks ๋ฆฌ์คํธ์ ๊ธธ์ด๋ฅผ ์ถ๋ ฅํ๋ค.
๐พ ๋๋์
- heapq๋ฅผ ์ฌ์ฉํ์ฌ ์ฌ๊ทํธ์ถ์ ํตํด ๋ต์ ๊ตฌํ๋ ๋ฌธ์ ์์ต๋๋ค.
- ๋ง๋๊ธฐ๋ฅผ ์๋ฅด๋ ๋ฐฉ๋ฒ์ ์ถฉ์คํ ๊ตฌํํ์ฌ ์ฌ๊ทํธ์ถํ๋ ๋ฐฉ๋ฒ์ ์ฌ์ฉํ๋ค๋ฉด ์ด๋ ต์ง ์๊ฒ ํ ์ ์๋ ๋ฌธ์ ์์ต๋๋ค.