[백준 18429] 근손실 - Python

문제 보기

[사용한 알고리즘]

순열(permutation)

 

[문제 접근]

운동 키트를 순서대로 나열할 수 있는 모든 경우의 수를 구한 후 조건 검사를 하는 문제입니다. N의 최댓값이 8이기 때문에 순열을 사용해도 시간 복잡도가 여유로웠습니다.

 

[알고리즘]

1. 순열을 통해 운동 키트 나열 순서를 구합니다.

2. 해당 순서로 운동을 수행하였을 때 중량 500을 유지할 수 있는지 확인합니다.

3. 중량 500을 유지할 수 있는 순서의 수를 출력합니다.

 

[코드]

import sys
from itertools import permutations


if __name__ == "__main__":
    n, k = map(int, sys.stdin.readline().split())
    array = list(map(int, sys.stdin.readline().split()))

    answer = 0
    for data in permutations(array, n):
        weight = 500
        flag = True
        for i in range(n):
            weight += data[i]  # 중량 증가
            weight -= k  # 중량 감소
            if weight < 500:  # 500 이상 확인
                flag = False
                break
        if flag:
            answer += 1

    print(answer)