Part6.5_완전탐색_깊이,넓이 우선탐색활용_동전분배하기(DFS)
12029 단어 CodingTestalgorithmpythonCodingTest
내가 생각한 코드
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. 변수 작작 만들자?ㅋㅋㅋ
Author And Source
이 문제에 관하여(Part6.5_완전탐색_깊이,넓이 우선탐색활용_동전분배하기(DFS)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@angel_eugnen/Part6.5완전탐색깊이넓이-우선탐색활용동전분배하기DFS저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)