삼성 SW역량테스트 기출 / 2017 하반기 오전 1번 문제 조삼모사 - 조합, 백트래킹 / Python 파이썬

 

*문제 출처는 삼성전자, 코드트리에 있습니다.

 

삼멘 2일차

문제 제목: 조삼모사

문제 사이트: https://www.codetree.ai/training-field/frequent-problems/problems/three-at-dawn-and-four-at-dusk/description?page=3&pageSize=20

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

 

---

나의 풀이

 

나는 아침, 점심으로 만들 조합을 구현하고,

그 조합 내에서 순열로 map에 있는 각각의 피로도를 구했다

 

삼성에 자주 나오는 조합, 순열 구현에 대한거니 풀면서 코드로 조합과 순열 구현 방법을 익혔음 ㅎㅎ

 

그리고 재귀함수로 나타낼때 함수 마지막 끝에 return 안하면 None 으로 반환되니까 그 부분 조심,,,

 

import sys
input = sys.stdin.readline

n = int(input())
maps = [list(map(int,input().split())) for _ in range(n)]
com_arr = []
num_lst = [i for i in range(n)]

# 아침, 저녁에서 각각의 조합을 만들기
def combination(length,new_lst,c):
    global com_arr
    if len(new_lst) == length:
        com_arr.append(new_lst)
        return
    for i in range(c,len(num_lst)):
        combination(length,new_lst + [num_lst[i]],i+1)

combination(n//2,[],0)
# print(com_arr)

# 각 조합 내에서 더하는 경우 (순열)
def permutation(lenght,new_list,comb_arr,per_arr):
    if len(new_list) == lenght:
        per_arr.append(new_list)
        return per_arr
    for i in range(len(comb_arr)):
        if comb_arr[i] not in new_list:
            per_arr = permutation(lenght,new_list + [comb_arr[i]],comb_arr,per_arr)
    return per_arr
answer = 1e9
def calcultation(lst1,lst2): # 각 조합에서 순열대로 맵 안의 값을 가져와 더하고 값 비교
    global answer
    sum1 = 0
    sum2 = 0
    for i in lst1:
        sum1 += maps[i[0]][i[1]]
        
    for i in lst2:
        sum2 += maps[i[0]][i[1]]
    
    answer = min(answer,abs(sum1-sum2))

for com in com_arr[:len(com_arr)//2]:
    tmp_per1 = permutation(2,[],com,[])
    tmp_per2 = permutation(2,[],list(set(num_lst) - set(com)),[])
    calcultation(tmp_per1,tmp_per2)
print(answer)

 

 

다른 풀이 - 코드트리 풀이 조합, 백트래킹

import sys

INT_MAX = sys.maxsize

# 변수 선언 및 입력
n = int(input())
p = [
    list(map(int, input().split()))
    for _ in range(n)
]
evening = [
    False for _ in range(n)
]

ans = INT_MAX


# 아침과 저녁 간의 힘듦의 차이를 계산합니다.
def calc():
    morning_sum = sum([
        p[i][j]  
        for i in range(n)
        for j in range(n)
        if not evening[i] and not evening[j]
    ])
    evening_sum = sum([
        p[i][j]  
        for i in range(n)
        for j in range(n)
        if evening[i] and evening[j]
    ])
        
    return abs(morning_sum - evening_sum)


def find_min(curr_idx, cnt):
    global ans
    
    # 정확히 아침 / 저녁으로 n / 2개씩 일이 나뉜 경우에만
    if cnt == n // 2:
        # 선택된 조합에 대해 합의 차이를 계산하여
        # 그 중 최솟값을 찾습니다.
        ans = min(ans, calc())
        return
    
    # n개에 대해 전부 결정했음에도
    # n / 2 개로 나뉘지 못한 경우라면
    # 바로 퇴각합니다.
    if curr_idx == n:
        return

    # curr_idx 번째 업무를 아침에 하는 경우
    find_min(curr_idx + 1, cnt)
    
    # curr_idx 번째 업무를 저녁에 하는 경우
    evening[curr_idx] = True
    find_min(curr_idx + 1, cnt + 1)
    evening[curr_idx] = False


find_min(0, 0)

# 출력:
print(ans)

---

※ 알아야 할 것

- 조합, 순열 - 코테 시험 전에 꾸준히 구현하기

- 재귀함수로 나타낼때 주의 (global 전역 변수 설정 안하고 함수 구현할때 주의해야함)

None만 나왔던 코드:

def permutation(lenght,new_list,comb_arr,per_arr):
    if len(new_list) == lenght:
        per_arr.append(new_list)
        print(per_arr)
        return per_arr
    for i in range(len(comb_arr)):
        if comb_arr[i] not in new_list:
            permutation(lenght,new_list + [comb_arr[i]],comb_arr,per_arr)

 

이후 해결한 코드:

def permutation(lenght, new_list, comb_arr, per_arr):
    if len(new_list) == lenght:
        per_arr.append(new_list)
        return per_arr
    for i in range(len(comb_arr)):
        if comb_arr[i] not in new_list:
            # 재귀 호출의 반환값을 받아서 반환하도록 수정
            per_arr = permutation(lenght, new_list + [comb_arr[i]], comb_arr, per_arr)
    return per_arr  # 최종적으로 per_arr를 반환