#3040. 백설공주와 일곱난쟁이들

링크: https://www.acmicpc.net/problem/3040
유형: 브루트 포스(완전탐색)
작성일시: 2022년 10월 16일 오전 12:25

문제

일곱 난쟁이의 모자에 쓰여져있는 숫자의 합 = 100

아홉 개의 수 중 합이 100이 되는 일곱 개의 수 찾기

입력

총 9개 줄에 1<= N <= 99 자연수 주어짐

모든 숫자는 서로 다름

답이 유일한 경우만 입력으로 주어짐

출력

모자에 쓰여져 있는 수 한 줄에 하나씩 출력

👀 풀이

내 코드

data = [0] * 9
for i in range(0,9): #순서대로 입력 받아 리스트에 저장
  data[i] = int(input())
sum = sum(data)

for j in range(8):
  for k in range(j+1, 9):
    if sum - (data[j] + data[k]) == 100: 
      fake1 = data[j]
      fake2 = data[k]
      break

data.remove(fake1)
data.remove(fake2)
data.sort()
for i in data:
  print(i)

다른 코드 #1

💡 **random.sample() 함수**

• sequence에서 지정한 숫자만큼의 요소들을 랜덤으로 뽑아 리스트로 반환해주는 함수
• import random
  • random.sample(sequence, k)
    • sequence: 리스트, 집합, range() 등 random의 범위가 될 sequence 입력
    • k: 반환될 리스트의 크기 입력

import random

data = [0] * 9
for i in range(0,9): #순서대로 입력 받아 리스트에 저장
  data[i] = int(input())

result = 0

while result != 100:
  real = random.sample(data,7)
  result = sum(real)

real = sorted(real)

for i in real:
  print(i)

다른 코드 #2

💡 집합 이용하기

import sys
from itertools import combinations

• cobinations(data, 원하는 list개수)

import sys
from itertools import combinations

input=sys.stdin.readline

def solve(case):
    if sum(case)==100:  #합이 100인 경우 
        case=list(case)
        case.sort()
        for i in case:
            print(int(i))
        return True
    return False
     

if __name__ == "__main__":
    data=set()  #집합 자료형
    for i in range(9):
        height=int(input().strip())     #양쪽 공백 모두 삭제
        data.add(height)
     
    for case in combinations(data,7):   #입력된 data중에서 중복없이 7개 선택
        if solve(case):
            break

브루트포스 알고리즘 (Brute Force)

• Brute : 무식한, Force : 힘
• 완전탐색 알고리즘. 가능한 모든 경우의 수를 모두 탐색하면서 요구조건에 충족되는 결과
• 종류
  • 선형구조 : 순차 탐색 👈 (ex. 10의 약수의 합)
  • 비선형구조 : 깊이 우선탐색 (DFS, Depth First Search), 너비 우선 탐색 (BFS, Breadth Frist Search)!