백준 2961 : 도영이가 만든 맛있는 음식 (Python)

본문 링크

def BackTracking(start,visit,S,B):
    global MIN_S_B


    if B!=0:
        MIN_S_B=min(MIN_S_B , abs(S-B) )

    for i in range(start,N):
        if not visit[i]:
            visit[i]=True
            BackTracking(start+1,visit , S*taste[i][0] , B+taste[i][1] )
            visit[i]=False

N=int(input())

taste=[ list(map(int,input().split())) for _ in range(N) ]
visit=[False]*N

MIN_S_B=int(1e9)

BackTracking(0,visit,1,0)
print(MIN_S_B)

📌 어떻게 접근할 것인가?

모든 경우의 수를 탐색하기 위해서 백트래킹을 사용했습니다.

반복문을 통해서 선택하지 않은 음식에 대해서 재귀를 수행하고 매번 차이의 최소값을 갱신해줍니다.

또한 음식은 한개당 한번만 사용해야 하므로 함수의 매개변수에 start 를 넣음으로써 똑같은것을 선택하지 않도록 했습니다.

visit 배열을 통해서 방문체크를 해주었습니다.