์ผ์ฑ SW ์ญ๋ ํ ์คํธ ๊ธฐ์ถ ๋ฌธ์ - 14889๋ฒ ์คํํธ์ ๋งํฌ
14889๋ฒ: ์คํํธ์ ๋งํฌ
์์ 2์ ๊ฒฝ์ฐ์ (1, 3, 6), (2, 4, 5)๋ก ํ์ ๋๋๋ฉด ๋๊ณ , ์์ 3์ ๊ฒฝ์ฐ์๋ (1, 2, 4, 5), (3, 6, 7, 8)๋ก ํ์ ๋๋๋ฉด ๋๋ค.
www.acmicpc.net
๋ฌธ์
์ค๋์ ์คํํธ๋งํฌ์ ๋ค๋๋ ์ฌ๋๋ค์ด ๋ชจ์ฌ์ ์ถ๊ตฌ๋ฅผ ํด๋ณด๋ ค๊ณ ํ๋ค. ์ถ๊ตฌ๋ ํ์ผ ์คํ์ ํ๊ณ ์๋ฌด ์ฐธ์๋ ์๋๋ค. ์ถ๊ตฌ๋ฅผ ํ๊ธฐ ์ํด ๋ชจ์ธ ์ฌ๋์ ์ด N๋ช ์ด๊ณ ์ ๊ธฐํ๊ฒ๋ N์ ์ง์์ด๋ค. ์ด์ N/2๋ช ์ผ๋ก ์ด๋ฃจ์ด์ง ์คํํธ ํ๊ณผ ๋งํฌ ํ์ผ๋ก ์ฌ๋๋ค์ ๋๋ ์ผ ํ๋ค.
BOJ๋ฅผ ์ด์ํ๋ ํ์ฌ ๋ต๊ฒ ์ฌ๋์๊ฒ ๋ฒํธ๋ฅผ 1๋ถํฐ N๊น์ง๋ก ๋ฐฐ์ ํ๊ณ , ์๋์ ๊ฐ์ ๋ฅ๋ ฅ์น๋ฅผ ์กฐ์ฌํ๋ค. ๋ฅ๋ ฅ์น Sij๋ i๋ฒ ์ฌ๋๊ณผ j๋ฒ ์ฌ๋์ด ๊ฐ์ ํ์ ์ํ์ ๋, ํ์ ๋ํด์ง๋ ๋ฅ๋ ฅ์น์ด๋ค. ํ์ ๋ฅ๋ ฅ์น๋ ํ์ ์ํ ๋ชจ๋ ์์ ๋ฅ๋ ฅ์น Sij์ ํฉ์ด๋ค. Sij๋ Sji์ ๋ค๋ฅผ ์๋ ์์ผ๋ฉฐ, i๋ฒ ์ฌ๋๊ณผ j๋ฒ ์ฌ๋์ด ๊ฐ์ ํ์ ์ํ์ ๋, ํ์ ๋ํด์ง๋ ๋ฅ๋ ฅ์น๋ Sij์ Sji์ด๋ค.
N=4์ด๊ณ , S๊ฐ ์๋์ ๊ฐ์ ๊ฒฝ์ฐ๋ฅผ ์ดํด๋ณด์.
์๋ฅผ ๋ค์ด, 1, 2๋ฒ์ด ์คํํธ ํ, 3, 4๋ฒ์ด ๋งํฌ ํ์ ์ํ ๊ฒฝ์ฐ์ ๋ ํ์ ๋ฅ๋ ฅ์น๋ ์๋์ ๊ฐ๋ค.
- ์คํํธ ํ: S12 + S21 = 1 + 4 = 5
- ๋งํฌ ํ: S34 + S43 = 2 + 5 = 7
1, 3๋ฒ์ด ์คํํธ ํ, 2, 4๋ฒ์ด ๋งํฌ ํ์ ์ํ๋ฉด, ๋ ํ์ ๋ฅ๋ ฅ์น๋ ์๋์ ๊ฐ๋ค.
- ์คํํธ ํ: S13 + S31 = 2 + 7 = 9
- ๋งํฌ ํ: S24 + S42 = 6 + 4 = 10
์ถ๊ตฌ๋ฅผ ์ฌ๋ฏธ์๊ฒ ํ๊ธฐ ์ํด์ ์คํํธ ํ์ ๋ฅ๋ ฅ์น์ ๋งํฌ ํ์ ๋ฅ๋ ฅ์น์ ์ฐจ์ด๋ฅผ ์ต์๋ก ํ๋ ค๊ณ ํ๋ค. ์์ ์์ ์ ๊ฐ์ ๊ฒฝ์ฐ์๋ 1, 4๋ฒ์ด ์คํํธ ํ, 2, 3๋ฒ ํ์ด ๋งํฌ ํ์ ์ํ๋ฉด ์คํํธ ํ์ ๋ฅ๋ ฅ์น๋ 6, ๋งํฌ ํ์ ๋ฅ๋ ฅ์น๋ 6์ด ๋์ด์ ์ฐจ์ด๊ฐ 0์ด ๋๊ณ ์ด ๊ฐ์ด ์ต์์ด๋ค.
์ ๋ ฅ
์ฒซ์งธ ์ค์ N(4 ≤ N ≤ 20, N์ ์ง์)์ด ์ฃผ์ด์ง๋ค. ๋์งธ ์ค๋ถํฐ N๊ฐ์ ์ค์ S๊ฐ ์ฃผ์ด์ง๋ค. ๊ฐ ์ค์ N๊ฐ์ ์๋ก ์ด๋ฃจ์ด์ ธ ์๊ณ , i๋ฒ ์ค์ j๋ฒ์งธ ์๋ Sij ์ด๋ค. Sii๋ ํญ์ 0์ด๊ณ , ๋๋จธ์ง Sij๋ 1๋ณด๋ค ํฌ๊ฑฐ๋ ๊ฐ๊ณ , 100๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ์ ์์ด๋ค.
์ถ๋ ฅ
์ฒซ์งธ ์ค์ ์คํํธ ํ๊ณผ ๋งํฌ ํ์ ๋ฅ๋ ฅ์น์ ์ฐจ์ด์ ์ต์๊ฐ์ ์ถ๋ ฅํ๋ค.
์์ ์ ๋ ฅ1
4
0 1 2 3
4 0 5 6
7 1 0 2
3 4 5 0
์์ ์ถ๋ ฅ1
0
ํ์ด
- ์กฐํฉ ์ฌ์ฉํ๊ธฐ
from itertools import combinations
n = int(input())
arr = []
for i in range(n):
arr.append(list(map(int, input().split())))
# ๋์ ํ์ด - 1) ์กฐํฉ ์ฌ์ฉ
# 1, 2 / 3, 4 ๋ก ๋๋๋ฉด 1,2 + 2,1 ์ด๋ 3,4 + 4,3 ๊ฐ ๋น๊ตํด์ ๋์ด ๋บ ๊ฐ์ ๋ฐฐ์ด์ ๋ฃ์ด์ค๋ค
# ๋ฐฐ์ด ์ค ์ต์๊ฐ ๋ฐํํ๋ฉด ์ ๋ต min()
members = list(range(n)) # ์ ์ฒด ๋ฉค๋ฒ๋ฅผ ํฌํจํ๋ ๋ฆฌ์คํธ ์์ฑ
result = [] # start - link ๊ฐ์ ๋ด์ ๋ฐฐ์ด
for s in combinations(members, n // 2):
start, link = 0, 0
l = list(set(members) - set(s))
for i in combinations(s, 2): # ์คํํธํ
start += arr[i[0]][i[1]]
start += arr[i[1]][i[0]]
for j in combinations(l, 2): # ๋งํฌํ
link += arr[j[0]][j[1]]
link += arr[j[1]][j[0]]
# ๋ฅ๋ ฅ์น ์ฐจ ๊ตฌํ๊ธฐ
if start > link:
result.append(start - link)
else:
result.append(link - start)
# ๋ฅ๋ ฅ์น ์ฐจ ์ค ์ต์๊ฐ ์ถ๋ ฅ
print(min(result))
๋ค๋ฅธ ์ฌ๋์ ํ์ด
- ๋ฐฑํธ๋ํน ์ฌ์ฉ : ๋ฐฑํธ๋ํน ์ข ๋ ์ฐ์ตํด๋ณด์,,
- zip() ํจ์ ์ฌ์ฉ : ์ด ๋ฌธ์ ๋ฅผ ํตํด zip()ํจ์๋ผ๋ ๊ฒ์ ์ฒ์ ์๊ฒ๋์๋ค
#### ๋ค๋ฅธ ์ฌ๋์ ํ์ด
# 2) ๋ฐฑํธ๋ํน
def dfs(depth, idx):
global min_diff
if depth == n//2:
power1, power2 = 0, 0
for i in range(n):
for j in range(n):
if visited[i] and visited[j]:
power1 += graph[i][j]
elif not visited[i] and not visited[j]:
power2 += graph[i][j]
min_diff = min(min_diff, abs(power1-power2))
return
for i in range(idx, n):
if not visited[i]:
visited[i] = True
dfs(depth+1, i+1)
visited[i] = False
n = int(input())
visited = [False for _ in range(n)]
graph = [list(map(int, input().split())) for _ in range(n)]
min_diff = int(1e9)
dfs(0, 0)
print(min_diff)
# 3) zip() ํจ์ ์ด์ฉ
from sys import stdin
from itertools import combinations
n = int(stdin.readline())
s = [list(map(int, stdin.readline().split())) for _ in range(n)]
member_stat = [sum(i) + sum(j) for i, j in zip(s, zip(*s))]
total_stat = sum(member_stat) // 2
res = 1e9
for c in combinations(member_stat[:-1], n // 2):
res = min(res, abs(total_stat - sum(c)))
print(res)
์ฐธ๊ณ ์ฌ์ดํธ
- zip() ํจ์
ํ์ด์ฌ์ zip() ๋ด์ฅ ํจ์๋ก ๋ฐ์ดํฐ ์ฎ๊ธฐ
Engineering Blog by Dale Seo
www.daleseo.com
- ๋ฌธ์ ํ์ด
[๋ฐฑ์ค] 14889 ํ์ด์ฌ(python) : ์คํํธ์ ๋งํฌ - (โ )
14889๋ฒ : ์คํํธ์ ๋งํฌ ๋ฐฑํธ๋ํน์ ์ด์ฉํ ํ์ด) import sys n = int(sys.stdin.readline()) graph = [ list(map(int, sys.stdin.readline().split())) for _ in range(n) ] visit = [ False for _ in range(n) ] #1 min_value = sys.maxsize #2 def backT
hgk5722.tistory.com
BOJ - ์คํํธ์ ๋งํฌ 14889๋ฒ (python)
โ ๋ฌธ์ - ๋ฐฑ์ค ์คํํธ์ ๋งํฌ 14889๋ฒ - python ํ์ด๋ฒ ์ถ์ฒ (https://www.acmicpc.net/problem/14889) 14889๋ฒ: ์คํํธ์ ๋งํฌ ์์ 2์ ๊ฒฝ์ฐ์ (1, 3, 6), (2, 4, 5)๋ก ํ์ ๋๋๋ฉด ๋๊ณ , ์์ 3์ ๊ฒฝ์ฐ์๋ (1, 2, 4, 5), (
developer-ellen.tistory.com
์๊ณ ๋ฆฌ์ฆ ๋ถ๋ฅ
- ๋ธ๋ฃจํธํฌ์ค ์๊ณ ๋ฆฌ์ฆ
- ๋ฐฑํธ๋ํน