[백준] 2961.py : 도영이가 만든 맛있는 음식

www.acmicpc.net/problem/2961

2961번: 도영이가 만든 맛있는 음식

 

n = int(input())
s = []
# 재료 하나를 한 쌍으로써 리스트에 추가한다
for i in range(n) :
    s.append(list(map(int, input().split())))
# 모든 부분집합을 돌며 차이를 저장할 공간
ans = []

# slist 의 모든 부분집합을 재귀적으로 돌기
def count(sv, ssv, slist, len) :
    global ans
    if len == 0:
        return;
    else :
        for i in range(len) :
            # 자기 자신 추가
            ans.append(abs((slist[i][0] * sv) - (slist[i][1] + ssv)))
            # 자기 아래에 종속되어있는 애들을 또 추가
            count(slist[i][0] * sv , slist[i][1] + ssv, slist[i+1:], len-i-1)

# 돌려주면 ans 에 부분집합의 값들이 저장됨
count(1, 0, s, n)
# 최솟값 출력
print(min(ans))

# 그림으로 그려보면 다음과 같다
# 1 - 2 - 3 - 4 - 5
#           - 5
#       - 4 - 5
#       - 5
# 1 - 3 - 4
#       - 5
# 1 - 4 - 5
# 1 - 5

# 2 - 3 - 4 - 5
#       - 5
#   - 4 - 5
#   - 5

# ...

 

[Try]

1. 재귀호출을.. 어찌저찌 했다.. 시간이 꽤 오래 걸렸다. 한 1시간 반?

 

[Point]

1. 리스트.extend() 로 iterable 한 친구들을 붙여주는 방법이 있다

 

[More]

숏코딩 1페이지에 들어가있길래 신기해서 캡쳐!