Part6.5_완전탐색_깊이,넓이 우선탐색활용_동전분배하기(DFS)

내가 생각한 코드

import sys
sys.stdin = open("input.txt", "rt")

def DFS(L,idx):
    global res, stdNum
    if L == n :
        aSum = sum(sav[0])
        bSum = sum(sav[1])
        cSum = sum(sav[2])
        if aSum == bSum or aSum == cSum or bSum == cSum:
            return
        else: 
            res =  max(aSum, bSum, cSum) -  min(aSum, bSum, cSum)
            if stdNum > res :
                stdNum = res
    else :
        for x in range(3):
            sav[x].append(list[idx])
            DFS(L+1, idx+1)
            sav[x].pop()
         
if __name__ == "__main__":
    res = 0
    stdNum = 2147000000
    list = []
    n = int(input())
    sav = [[] for _ in range(3)]

    for _ in range(n):
        tmp = int(input())
        list.append(tmp)

    DFS(0,0)
    print( stdNum)

다행 ..

선생님 코드

문제가 DFS 같다면 상태트리를 그려야 하고 그대로 구현해야 한다,

import sys
sys.stdin = open("input.txt", "rt")

def DFS(L):
    global res
    if L == n :
        cha=max(money)-min(money)
        if cha < res:
            tmp = set() # 자료구조
            for x in money:
                tmp.add(x) #money에 들어가 있는 3가지 값을 set 자료 구조에 넣어주어 중복 있는지 확인
            if len(tmp) == 3:
                res = cha # 길이가 3이어야만 res 가 cha가 될 수 있음
    else: 
        for i in range(3):
            money[i] += coin[L] # int 니까 그냥 append가 아니라 += 하면 더 쉽잖아 ㅋㅋㅋ 바보야 ㅋㅋㅋㅋ
            DFS(L+1)
            money[i]-=coin[L]
         
if __name__ == "__main__":
    n = int(input())    
    coin = []
    money = [0]*3

    for _ in range(n):
        coin.append(int(input()))
    res = 2147000000
    DFS(0)
    print(res)

와 역시 훨씬 깔끔해..
안유진 개선해야 될 부분
1. 굳이 이차원 배열만든 것 >> 일차원 배열로 가능
2. 굳이 append 하며 sum을 한번 더 한것 >> += 으로 하면 된다.
3. 굳이 중복 or로 확인한 것 >> set으로 하면 된다.
4. 변수 작작 만들자?ㅋㅋㅋ