[코테준비]2. 백준- 스타트와 링크(14889) python "삼성 SW 역량 테스트 기출 문제"

스타트와 링크

• 링크:https://www.acmicpc.net/problem/14889
• 난이도:실버2
• 분류: 브루트포스, 백트레킹
• 직접 푼 여부: O (풀이1만)
• 언어: python

 

1. 풀이1: itertools사용 예시

itertools는 쉽게 풀 수 있지만, 삼성에선 사용할 수 없으니 다른 방법을 써야한다. 

import sys
from itertools import combinations

n = int(sys.stdin.readline())
score =[list(map(int, sys.stdin.readline().split())) for _ in range(n)]

diff = 100000 # 40000도 충분할 듯 
for combi in combinations(range(n), n//2):
    bb=set(range(n))-set(combi)
    ateam = 0
    bteam = 0
    
    for c in combinations(combi, 2):
        ateam += score[c[0]][c[1]]+score[c[1]][c[0]]
    for c in combinations(bb,2):
        bteam += score[c[0]][c[1]]+score[c[1]][c[0]]
    if abs(ateam-bteam)<diff:
        diff=abs(ateam-bteam)
print(diff)

2. 풀이2 : itertools사용 안하고 풀기

- 해당 방법은 따로 공부후 업데이트 예정! 

 

 

 

* ps. 글에 있는 삼성 합격! 은 합격하고 싶어서 만든 것이다. 아직 합격 안했습니다.! 보시는 분들도 다 합격하세요 🍀