[코드트리 삼성기출] 조삼모사

📌문제 출처

코드트리 삼성 SW 역량테스트 기출문제
https://www.codetree.ai/training-field/frequent-problems/problems/three-at-dawn-and-four-at-dusk

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

📗 풀이 코드

input = open(0).readline

def combinations(ls,n_pick): # ls라는 list에서 n_pick개를 뽑는 조합의 수
    if n_pick == 2 : # 2개만 뽑는 경우
        res = []
        for i in range(len(ls)):
            for j in range(i+1,len(ls)):
                res.append([ls[i],ls[j]])
        return res # 두개 조합의 배열이 담긴 배열
    res = []
    for i in range(len(ls)-n_pick+1):
        res += [[ls[i]] + x for x in combinations(ls[i+1:],n_pick-1)]
    return res

def solution(n, p):
    morning_works = combinations(range(n),n//2) # n개의 index 중에 n//2개를 뽑는 경우
    ans = []
    total_set = set(range(n))
    for morning in morning_works: # 아침 작업 조합을 반복하면서
        evening = list(total_set - set(morning)) # 저녁 직업 조합을 뽑고
        hard_m, hard_e = 0,0 # 아침 강도, 저녁 강도
        for i in range(n//2):
            for j in range(n//2): # 각 작업 조합에서
                if i != j :
                    hard_m += p[morning[i]][morning[j]]
                    hard_e += p[evening[i]][evening[j]]
        ans.append(abs(hard_m-hard_e))
    return min(ans)

if __name__ == '__main__':
    n = int(input())
    p = [list(map(int, input().split())) for _ in range(n)]
    print(solution(n,p))

 

💯 풀이 설명

• 조합 함수를 직접 만들고 강도를 직접 비교