[BOJ] 2309 일곱 난쟁이 - python

TIP

문제 링크 (opens new window)

문제 설명

문제 요약

9개의 정수값이 주어졌을때 합이 100이 되게하는 7개의 정수값을 구하라.

문제 접근

매우 쉬운 문제이다. 그래서 정답을 맞추는것 자체보다는 여러 구현을 해보면서 순열조합 연습하는 목적으로 문제를 풀었다.

풀이1 ( next_permutation 구현)

난쟁이를 선택할수도있고 선택 하지않을수도있다. 선택여부를 저장하는 select 리스트를 만들어서 이 아이디어를 표현할수있다. select[i] 가 1 이라면 i 번째 난쟁이를 일곱난쟁이 멤버로 선택 한것이고, 0 이라면 i 번째 난쟁이를 선택하지않은것이다. 예를들어 select=[0,0,1,1,1,1,1] 이라면 i=2인 난쟁이부터 i=6인 난쟁이까지 선택하였다는 것이다.

난쟁이를 고르는 다음 경우을 구하기위해서는 select 에 next_permutation 을 하여 답을 구해나갈수있다.

파이썬은 c++ STL 의 next_permutation 과 동일한 기능을 하는 함수를 제공해주지않는다.
그래서 직접 구현해야한다. 물론 itertools 패키지 에서 permutations 함수와 combinations 함수를 제공해주지만, 두 함수는 입력의 모든 요소가 서로 다르다고 전제하여 구현이 되었다는 점에서 c++의 next_permutation 과 다르다.

a = [0, 0, 1]
b = list(itertools.permutations(a))
# [(0, 0, 1), (0, 1, 0), (0, 0, 1), (0, 1, 0), (1, 0, 0),(1, 0, 0)]
# 같은 순열이 두개씩 생기는것을 볼수있다.  

풀이1 로직

1. 표현: 난쟁이를 골랐는지 고르지 않았는지를 1 과 0 으로 표현하고, 이를 select 리스트에 저장한다. 또한 입력으로 주어지는 키는 hs 라는 리스트에 저장하겠다
2. 초기값: 0번째, 1번째 난쟁이가 0이고 나머지 난쟁이가 1인 경우

hs = [..입력 키 저장..]
select = [0, 0, 1, 1, 1, 1, 1]
		   # select[i] 가 1 이라면 i 번째 값을 골랐다는 것 

3. 고른 난쟁이들(select[i]가 1인 난쟁이들)의 키가 100이라면 일곱 난쟁이들을 출력해주고 종료한다.
4. 아니라면 next_permutations(select)를 호출해서 다음으로 고를수있는 경우 만든다

풀이1 소스코드

TIP

BOJ 제출소스 (opens new window)

def main():
    # 입력으로 주어지는 난쟁이들의 키
    hs = []
    for _ in range(9):
        hs.append(int(input()))
    hs.sort()
    select = [0]*2 + [1]*7
    while True:
        if is_ans(hs, select):
            print('\n'.join([str(hs[i]) for i in range(9)
                                    if select[i]]))
            break
        if not next_permutation(select):
            break

def is_ans(hs, select):
    return sum([hs[i] for i in range(9)
                if select[i]]) == 100

def next_permutation(a):
    n = len(a)

    # find i
    i = n - 1
    while i > 0 and not (a[i-1] < a[i]):
        i -= 1
    if i == 0:
        return False

    # find j. bigger than a[i-1]
    def find_first_bigger(seq, target):
        j = n - 1
        while j > 0 and not (seq[j] > seq[i-1]):
            j -= 1
        return j
    j = find_first_bigger(a, a[i])

    # swap
    a[i-1], a[j] = a[j], a[i-1]
    
    def reverse_inplace(a, start, end):
        while start < end:
            a[start], a[end] = a[end], a[start]
            start += 1
            end -= 1
    reverse_inplace(a, i, n-1)
    
    return True
   
main()

풀이2 ( itertools.combinations 이용 )

두 난쟁이를 뽑은다음, 전체 합에서 두 난쟁이의 키를 뺀 결과가 100이 되면 두 난쟁이를 제외한 난쟁이들이 일곱난쟁이이다.

TIP

BOJ 제출소스 (opens new window)

import itertools
import sys
input = sys.stdin.readline

def main():
    NINE = 9
    heights = []
    for _ in range(NINE):
        heights.append(int(input()))
    heights.sort()

    sum_h = sum(heights)

    combinations_h = itertools.combinations(heights, 2)

    for a, b in combinations_h:
        if sum_h - a - b == 100:
            print('\n'.join([str(h) for h in heights
                                if h != a and h != b]))
            break

main()

풀이3 ( combinations 직접 구현 )

TIP

BOJ 제출소스 (opens new window)

# ...
# main 함수는 풀이2와 동일함
# ...
def combinations(seq, r):
    ret = []
    n = len(seq)
    tmp = [0]*r
    visited = [False]*n
    def _combinations(chosen, start):
        if len(chosen) == r:
            ret.append(chosen[:])
            return
        for i in range(start, n):
            if visited[i]:
                continue
            visited[i] = True
            chosen.append(seq[i])
            _combinations(chosen, start=i+1)
            chosen.pop()
            visited[i] = False
    _combinations(chosen=[], start=0)
    return ret