[BOJ]#2309 일곱 난쟁이Python

현지·2021년 2월 25일

BOJ

목록 보기

7/44

문제

https://www.acmicpc.net/problem/2309

왕비를 피해 일곱 난쟁이들과 함께 평화롭게 생활하고 있던 백설공주에게 위기가 찾아왔다. 일과를 마치고 돌아온 난쟁이가 일곱 명이 아닌 아홉 명이었던 것이다.

아홉 명의 난쟁이는 모두 자신이 "백설 공주와 일곱 난쟁이"의 주인공이라고 주장했다. 뛰어난 수학적 직관력을 가지고 있던 백설공주는, 다행스럽게도 일곱 난쟁이의 키의 합이 100이 됨을 기억해 냈다.

아홉 난쟁이의 키가 주어졌을 때, 백설공주를 도와 일곱 난쟁이를 찾는 프로그램을 작성하시오.

입력

아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다.

출력

일곱 난쟁이의 키를 오름차순으로 출력한다. 일곱 난쟁이를 찾을 수 없는 경우는 없다.

아이디어

9명의 난쟁이 중 7명을 찾아야한다.

9명 모두의 키를 더해서 100을 뺀다.(=num)

num값이 일곱 난쟁이가 아닌, 두 난쟁이의 키의 합과 같으면 그 두 명을 제외하면 된다.

num에서 순서대로 리스트 요소(n)를 하나씩 뺀 값(num-n)이 리스트에 존재하면 그 두 키(n, num-n)를 제외한다.

내 코드(Python)

data=[0]*9
for i in range(0,9):	#순서대로 입력받아 리스트에 저장
    data[i]=int(input())
   
num=sum(data)-100	#9명 키의 합에서 100을 뺀다.
for i in range(0,9):
    n=data[i]	#리스트 순서대로 값 지정
    data.remove(n)	#리스트에서 삭제
    if num-n in data:	#num-n이 n을 제외한 data리스트에 존재하면
        data.remove(num-n)	#num-n도 data리스트에서 삭제
        break
    else:	#num-n이 n을 제외한 data리스트에 존재하지 않으면 
        data.insert(i,n)	#다시 같은 자리에 n추가(data리스트 복구)
  
data.sort()	#data리스트를 순서대로 정렬
for i in data:	#data리스트 출력
    print(i, sep='\n')

다른 코드(Python) #1

data=[]
for i in range(9):
    data.append(int(input()))

dataSum=sum(data)
one=0
two=0
for i in range(8):	#모든 수의 경우를 따진다.  
    for j in range(i+1, 9):
        if dataSum-(data[i]+data[j])==100:    #두 수를 뺀 값이 100이면
            one=data[i]
            two=data[j]
data.remove(one)	#리스트에서 제외
data.remove(two)
data.sort()
for i in data:
    print(i)

다른 코드(Python) #2

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