7
7 1297
9 1230
4 5780
4 1235
3 7652
8 979
10 977
-->답 : 439
10
2 300
2 300
2 300
2 300
2 300
2 300
2 300
2 300
2 300
2 300
-->답 : 298
그 음식의 신맛은 사용한 재료의 신맛의 곱이고, 쓴맛은 합이다.
재료를 적절히 섞어서 요리의 신맛과 쓴맛의 "차이를 작게" 만들려고 한다
신맛과 쓴맛의 차이가 가장 작은 요리를 만드는 프로그램을 작성하시오.
절댓값(A-B) 차가 가장 작은 것을 결과물로
테스트케이스들은 맞았는데, 히든테케에서 틀렸다!
생각한게 일부 맞긴 했는데, 틀린 이유는
나는 재료안에 맛을 따로 따로 combinations하고, 각각 combinations 결과로 브루트포스 계산함
즉, A, B 따로 구해서 A, B의 카디널리티곱처럼 수행했음
=> 근데 이게 아님!!
=> 하나의 재료에 두 맛이 pair로 있는 것!!! 따로 combination하면 안된다!!
핵심아이디어
for cases in combinations(list(range(n)), i):
from itertools import combinations
import sys
input = sys.stdin.readline
n = int(input())
S_tmp = []
B_tmp = []
S = []
B = []
for _ in range(n):
s, b = map(int, input().split())
S_tmp.append(s)
B_tmp.append(b)
for i in range(1, n+1): # 최소 하나이상 선택(만약 에러라면 0부터 n+1까지)
for j in combinations(S_tmp, i):
multi = 1
for k in j:
multi *= k
S.append(multi)
for j in combinations(B_tmp, i):
B.append(sum(j))
answer = 1000000000
for s in S:
for b in B:
if s != b:
answer = min(answer, abs(s-b))
print(answer)
from itertools import combinations
import sys
input = sys.stdin.readline
n = int(input())
S_tmp = []
B_tmp = []
S = []
B = []
for _ in range(n):
s, b = map(int, input().split())
S_tmp.append(s)
B_tmp.append(b)
for i in range(1, n+1): # 최소 하나이상 선택(만약 에러라면 0부터 n+1까지)
for j in combinations(list(range(n)), i):
multi = 1
suma = 0
for k in j:
multi *= S_tmp[k]
suma += B_tmp[k]
# 애초에 S와 B를 따로가면 안된다
S.append(multi)
B.append(suma)
answer = 1000000000
# 이렇게 브루트포스하면 안된다 ==> 두 맛이 포함된 재료는 한 묶음이므로!
for s in S:
for b in B:
answer = min(answer, abs(s-b))
print(answer)
from itertools import combinations
import sys
input = sys.stdin.readline
n = int(input())
S = []
B = []
for _ in range(n):
s, b = map(int, input().split())
S.append(s)
B.append(b)
answer = 1000000000
for i in range(1, n+1): # 최소 하나이상 선택(만약 에러라면 0부터 n+1까지)
# 내가 틀린 이유 : 재료안에 맛을 따로 combinations해서 계산함 => 재료에 두 맛이 pair로 있는 것!!!
for cases in combinations(list(range(n)), i): # (중요) 배열의 인덱스로 combination하는 방법
s = 1
b = 0
for j in cases:
s *= S[j]
b += B[j]
answer = min(answer, abs(s-b))
print(answer)