백준_2961 (도영이가 만든 맛있는 음식_실버2_브루트포스_인덱스로 접근하는 combinations_중요)

RostoryT·2022년 8월 15일
0

Brute force

목록 보기
16/18


히든 테스트케이스

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.append
    쓴맛끼리 모든 경우의 수 조합해서 더해준걸 B.append ~> 이때 combinations(arr, i<--)

절댓값(A-B) 차가 가장 작은 것을 결과물로

  • 테스트케이스들은 맞았는데, 히든테케에서 틀렸다!

  • 생각한게 일부 맞긴 했는데, 틀린 이유
    나는 재료안에 맛을 따로 따로 combinations하고, 각각 combinations 결과로 브루트포스 계산함
    즉, A, B 따로 구해서 A, B의 카디널리티곱처럼 수행했음
    => 근데 이게 아님!!
    => 하나의 재료에 두 맛이 pair로 있는 것!!! 따로 combination하면 안된다!!

  • 핵심아이디어

    • "인덱스에 대한 combinations" 를 만들어서 공동으로 진행
for cases in combinations(list(range(n)), i):

솔루션 코드 - 틀린

  • 이렇게 따로따로 combinations해서 하면 안된다!
    • 재료 하나에 맛이 두 가지이니까!!! --> T라는 재료에서 맛만 따로 추출할순 없잖아
  • 틀린코드 1
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)
  • 틀린코드 2(솔루션보고 바꿨는데 답은 바뀌지않음)
    • 이유는 위 코드와 마찬가지로 구분해서 combinations하고 카디널리티처럼 했기 때문
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)



솔루션 코드 - 블로그

  • 내가 왜 틀렸는지 이해했다..! 기초적인 상식?생각?의 문제였음
  • 핵심은 for cases in combinations(list(range(n)), i):
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)


profile
Do My Best

0개의 댓글