๋ฌธ์ ๋งํฌ
2961๋ฒ: ๋์์ด๊ฐ ๋ง๋ ๋ง์๋ ์์
๋ฌธ์ ์์ฝ
๋์์ด๋ ์ฌ๋ฃ N๊ฐ๋ก ์๋ฆฌ๋ฅผ ๋ง๋ค๋ ค๊ณ ํ๋ค. ๊ฐ ์ฌ๋ฃ์ ์ ๋ง๊ณผ(S) ์ด๋ง(B)์ ์๊ณ ์๊ณ , ์๋ฆฌ์ ์ ๋ง์ ๊ฐ ์ฌ๋ฃ ์ ๋ง์ ๊ณฑ์ด๊ณ , ์ด๋ง์ ํฉ์ผ ๋, ์ ๋ง๊ณผ ์ด๋ง์ ์ฐจ์ด์ ์ต์๊ฐ์ ๊ตฌํ๋ผ.
โป ๋จ, ์๋ฆฌ๋ฅผ ์์ฑํ๊ธฐ ์ํด ์ฌ๋ฃ๋ 1๊ฐ ์ด์ ์ฌ์ฉํ์ฌ์ผ ํ๋ค.
โป N(1 ≤ N ≤ 10)์ด๊ณ , ๋ชจ๋ ์ฌ๋ฃ์ ์ ๋ง๊ณผ ์ด๋ง์ ํฉ์ 1,000,000,000 ์์ ์์ ์ ์์ด๋ค.
ํ์ด ์ค๋ช
์ด ๋ฌธ์ ์ ์๊ณ ๋ฆฌ์ฆ ๋ถ๋ฅ๋ ๋ธ๋ฃจํธํฌ์ค, ๋นํธ๋ง์คํน, ๋ฐฑํธ๋ํน์ด์์ผ๋, ๊ฐ์ง์น๊ธฐ ์กฐ๊ฑด์ ์ฐพ์ง ๋ชปํ์ฌ(๋ ์ฌ๋ฆฐ ๋ชจ๋ ๊ฐ์ค ์กฐ๊ฑด์ ์์ธ๊ฐ ๋ฐ์) ๋ธ๋ฃจํธํฌ์ค ๋ฐฉ์์ผ๋ก ํด๊ฒฐํ์๋ค.
์ด ๋ฌธ์ ์์ 1, 2, ..., N๊ฐ์ ์ฌ๋ฃ๋ฅผ ์ ํํ๋ ๊ฐ ๊ฒฝ์ฐ์ ๋ํด, ๋ชจ๋ ๊ฒฝ์ฐ๋ฅผ ํ์ํด์ผ ํ์์ผ๋ฉฐ, ์ด๋ฅผ ์ฌ๊ท ํจ์๋ก ํธ๋ ๋ฐฉ๋ฒ์ ๋ ์ฌ๋ ค์ ๊ตฌํํ์๋ค.
N=int(input())
ingredients=[]
for _ in range(N):
S, B=map(int, input().split())
ingredients.append((S, B))
flavor=999999999
# ...(์ค๋ต)...
for k in range(1, N+1):
for i in range(N-k+1):
add_ingredient(1, 0, k, i)
print(flavor)
์ ๋ ฅ ์ฌํญ๋ค์ ์ ์ฅํ๊ณ , ์ ๋ง๊ณผ ์ด๋ง์ ์ฐจ์ด(flavor) ์ต์๊ฐ์ ๊ตฌํ๋ ๊ฒ์ด๋ฏ๋ก ์ด๊ธฐ flavor๋ ์ ๋ ฅ๊ฐ ์ ํ์ ๋ฐ๋ฅธ ์ต๋๊ฐ์ธ 999999999์ผ๋ก ์ค์ ํ์๋ค.
์ฌ๊ทํจ์๋ ๋ค์๊ณผ ๊ฐ์ด ๊ตฌ์ฑ๋์ด ์๋ค.
add_ingredient(S, B, rest, next_ingredient)
S๋ ์ ๋ง, B๋ ์ด๋ง, rest๋ ๋ง์ ๋ฐ์๋์ด์ผ ํ๋ ๋จ์ ์ฌ๋ฃ ์๋ฅผ ์๋ฏธํ๋ฉฐ, next_ingredient๋ ingredients ๋ฆฌ์คํธ๋ฅผ ๊ธฐ์ค์ผ๋ก ๋ค์์ ๋ฃ์ ์ฌ๋ฃ์ index๋ฅผ ์๋ฏธํ๋ค.
def add_ingredient(S, B, rest, target_ingredient):
global flavor
cur_S, cur_B=ingredients[target_ingredient]
cur_S*=S
cur_B+=B
rest-=1
if rest==0:
cur_flavor=abs(cur_B-cur_S)
flavor=min(flavor, cur_flavor)
return 0
elif rest>0:
for i in range(target_ingredient+1, N-rest+1):
add_ingredient(cur_S, cur_B, rest, i)
flavor์ global variable๋ก ๋๊ณ , ์์ ํจ์์ ๊ฐ์ด rest==0์ด๋ฉด, ํด๋น ๊ฐ์ ์ ๋ฐ์ดํธํ๋ค.
rest>0์ธ ๊ฒฝ์ฐ์๋ ํ์ฌ target_ingredient+1์ธ index๋ถํฐ N-rest+1 ๊น์ง์ i์ ํํด ๋ค์ ์ฌ๊ทํจ์๋ฅผ ๋ฃ์์ผ๋ก์จ ingredient๊ฐ ์๋์น์๊ฒ ์ถ๊ฐ๋์ง ์๋ ์ฌ๋ก๋ฅผ ๋ฐฉ์งํ์๋ค.
๋ง์ฐฌ๊ฐ์ง๋ก ์ฒ์ ์ฌ๊ทํจ์ ์คํ์ํค๋ ๋ณธ๋ฌธ์์๋ N-k+1๊น์ง ๋ฒ์๋ฅผ ์ง์ ํจ์ผ๋ก์จ ์๋ํ ๊ฐฏ์์ ingredient๊ฐ flavor์ ๋ฐ์๋๊ฒ๋ํ์๋ค. (์ด๋ ๊ฒ ๋ฒ์๋ฅผ ๋ช ํํ ์ฃผ์ง ์์ผ๋ฉด ์ฝ๋์ ๋ฐ๋ผ indexError๋ ๋ฐ์ํ ์ ์๋ค.)
์ฌ๊ธฐ๊น์ง ์ฌ๊ท ํจ์๋ก ํผ ๋์ ๋ฐฉ์์ด์๊ณ , ๋ค๋ฅธ ์ฌ๋๋ค์ ํ์ด ๋ฐฉ์์ ์ดํด๋ณด๋ ๋ด๊ฐ ๋ ์ฌ๋ฆฌ์ง ๋ชปํ๋ ์ ๊ธฐํ ๋ฐฉ์์ด ์์๋ค.
๋นํธ ๋ง์คํน ๋ฐฉ์์ ํ์ด ์ค๋ช
import sys
input = sys.stdin.readline
#...(์ค๋ต)...
n=int(input())
tastes = []
for _ in range(n):
s,b = map(int,input().split())
tastes.append((s,b))
solution(n,tastes)
dasapcr ์ ์ ๋ถ์ ํ์ด์ธ๋ฐ,
ํต์ฌ์ ์ธ solution ํจ์ ๋ด์ฉ์ ์ ์ธํ ๋ต ์ฝ๋๋ ์์ ๊ฐ๋ค.
๋์ ๋ง์ฐฌ๊ฐ์ง๋ก tuple ์๋ฃํ์ผ๋ก S, B๋ฅผ ์ฎ์ด์ list์ ์ ์ฅํ์ จ๋ค.
def solution(n,tastes):
if n==1:
print(abs(tastes[0][0]-tastes[0][1]))
return
else:
result = sys.maxsize
for i in range(1,2**n):
sum1,sum2 = 1,0
for j in range(n):
if (i & 1 << j) != 0:
sum1 *= tastes[j][0]
sum2 += tastes[j][1]
result = min(result,abs(sum1-sum2))
print(result)
return
i๋ 2์ง์๋ก ๊ฐ์ฃผ๋์ด์, n๊ฐ ์ฌ๋ฃ์ ๋ชจ๋ ๊ฒฝ์ฐ์ ์๋ฅผ ํํํ ์ ์๋ค.
์๋ฅผ ๋ค์ด 00001001์ด๋ฉด 5๋ฒ์งธ์ 8๋ฒ์งธ ์ฌ๋ฃ๊ฐ ๋ค์ด๊ฐ๋ ์๋ฆฌ๋ผ๋ ๋ฐฉ์์ผ๋ก ํด์ํ๋ค.
๋นํธ AND ์ฐ์ฐ์(&)์ ๋นํธ left shift ์ฐ์ฐ์(<<) ์ค shift ์ฐ์ฐ์์ ์ฐ์ ์์๊ฐ ๋์ ๋จผ์ ๋ฐ์๋๋๋ฐ, ์ค๋ฌด์์๋ ๋ช ํํ๊ฒ ๊ดํธ๋ก ์ฐ์ฐ์ ์ฐ์ ์์๋ฅผ ๋ํ๋ธ๋ค๊ณ ํ๋ค.
์ํ์ ํ์ด์ ๊ธฐ๋ถ์ด ์ข์์ผ๋, ๋ค์ ํ์ด๋ฅผ ๊ฒํ ํ๋ ๊ณผ์ ์์ ๋ด ํ์ด์ ์ทจ์ฝ์ ์ผ ์ ์๋ ์์๋ค์ ํ์ ํ์๊ณ ์ด๋ฅผ ์ฌํ์ธํ ์ ์์๋ค. (์ค๋ต์ ๋์ถํ๋ ์์๋ ์๋์๊ณ , ์์ ์๊ฐ์ ๋ค์ ๋๋ฆด ์ ์๋ ๋นํจ์จ์ ์ธ ์์๋ฅผ ๊ฐ์ ํ์๋ค.)