Medical and Programming Study

바로 직전에 풀어보았던 GCD 합 문제처럼 combinations library를 이용하면 쉽게 풀 수 있는 문제였다.

from itertools import combinations    # 수학에서의 조합을 사용할 수 있게 해주는 library
import sys
input = sys.stdin.readline    # 시간 초과 error를 해결하기 위한 input함수 재정의

result = []    # 정답 저장

N = int(input())    # 수열 S의 크기
S = list(map(int, input().strip().split(' ')))    # 수열 S

for i in range(1, N+1):    # 수열 S의 크기만큼 반복
    for args in list(combinations(S, i)):    # 수열 S에서 i개를 꺼내어 조합
        result.append(sum(args))    # 조합으로 나온 수 i개를 합하여 나온 결과를 저장

result = set(sorted(result))    # 중복 제거를 위해 집합으로 변환

for i in range(1, max(result) + 2):    # 1부터 result의 결과보다 1 큰 수까지 반복
    if i not in result:    # 정수 i가 result에 존재하지 않을 경우 출력 후 마침
        print(i)
        break

combinations의 수학적 정의를 생각해보면, nCx에서 x가 n/2를 넘어가면 n-x로 바뀌는 경우 시간이 더 적게 소모된다.

해당 부분을 적용하면 시간적인 부분에서 더 감소하지 않을까 생각하여 다시 제출하였다.

from itertools import combinations    # 수학에서의 조합을 사용할 수 있게 해주는 library
import sys
input = sys.stdin.readline    # 시간 초과 error를 해결하기 위한 input함수 재정의

result = []    # 정답 저장

N = int(input())    # 수열 S의 크기
S = list(map(int, input().strip().split(' ')))    # 수열 S

for i in range(1, N+1):    # 수열 S의 크기만큼 반복
    if i > N/2:    # 현재 정수가 N/2보다 크다면
        for args in list(combinations(S, N-i)):    # 수열 S에서 N-i개를 꺼내어 조합
            result.append(sum(S) - sum(args))    # 조합으로 나온 수 i개를 합하여 나온 결과를 전체 수열의 합에 뺀 후 저장
    else:    # 현재 정수가 N/2보다 작다면
        for args in list(combinations(S, i)):    # 수열 S에서 i개를 꺼내어 조합
            result.append(sum(args))    # 조합으로 나온 수 i개를 합하여 나온 결과를 저장

result = set(sorted(result))    # 중복 제거를 위해 집합으로 변환

for i in range(1, max(result) + 2):    # 1부터 result의 결과보다 1 큰 수까지 반복
    if i not in result:    # 정수 i가 result에 존재하지 않을 경우 출력 후 마침
        print(i)
        break

이번에는 아이디어 적인 부분에서 나름 창의적으로 한 것 같아서 풀이를 공유하기 설렌다!

내가 생각한 아이디어는 다음과 같다.

1. 두 수를 분수꼴로 나타낸다. (이 때, 분수는 기약분수가 된다.)

2. 나눠진 수를 분자로 나누면 GCD 등장!

이 아이디어면 소수를 따로 판별할 필요 없이 가능하다.

예시를 두 개 들어서 설명해 보겠다.

숫자 30과 45가 있다고 가정해 보면, 1번에 의해 30/45인 2/3이 나타나게 된다.

이후 2번에 의해 30/2 = 15가 나타나게 되는데, 이는 GCD이다.

하나 더, 숫자 3과 7이 있다고 가정해 보면, 1번에 의해 3/7이 나타나게 된다.

이후 2번에 의해 3/3 = 1이 나타나게 되는데, 이 역시 GCD이다.

이 행위가 가능한 이유를 보면, "기약 분수"로 표현한다는 것 자체가 GCD로 나눠진 값이다.

즉, GCD로 나눠진 값을 원래 값으로 나누면 GCD가 나타나게 되는 것!

이 아이디어를 구현하기 위해서 combinations와 Fraction library를 import 하였다.

from itertools import combinations    # 수학에서의 조합을 사용할 수 있게 해주는 library
from fractions import Fraction    # 분수식으로 표현할 수 있게 해주는 library
import sys
input = sys.stdin.readline    # 시간 초과 error를 해결하기 위한 input함수 재정의

n = int(input())    # 테스트 케이스의 개수
for _ in range(n):
    answer = 0    # 정답을 저장하는 변수
    num, *numbers = map(int, input().strip().split(' '))    # 개수와 숫자들을 모두 입력받는 방법

    for (num1, num2) in list(combinations(numbers, 2)):    # numbers에서 2개씩 뽑는 조합을 진행
        f = Fraction(num1, num2)    # num1과 num2를 분수식으로 표현 (이 때, 기약분수로 표현됨)
        answer += num1 // f.numerator    # num1을 분자로 나눈다면 GCD (num2을 분모로 나눠도 동일)

    print(answer)    # 정답 출력

숫자를 입력받는 방법을 모른다면 Asterisk를 검색해보길 권장한다.