[BOJ][Python] 백준 23057번 - 도전 숫자왕

문제 링크: https://www.acmicpc.net/problem/23057

23057번: 도전 숫자왕

---

문제 풀이

심심해서 BOJ 들어갔다가 대회가 20분 남짓 남아서 딱 3문제 풀었다. 이 문제는 그 3문제 중 하나.

각설하고, 조합을 이용하여 N개의 수 중 1~N개를 선택하여 조합을 만들어주고 합을 구한다.
이때, 합이 중복될 수도 있으므로 set()을 이용하여 중복값을 없애주었다.
또한 1부터 M까지 반복문을 돌리려고 하면 시간 초과가 날 것이다. M은 최대 2,000,000,000이기 때문이다.
따라서 M에서 set()에 있는 길이를 빼준다.
즉, M - (조합으로 구할 수 있는 수의 개수)를 구하면 O(1)에 가능하다.

코드

	from itertools import combinations as c
	n = int(input())
	array = list(map(int, input().split()))
	m = sum(array)
	num = set()
	for i in range(1, n+1):
	for j in c(array, i):
	num.add(sum(j))
	print(m-len(num))

view raw 23057.py hosted with ❤ by GitHub