BJO 2437 저울
문제이해
N개의 저울추가 주어진다. 리스트에 담아서 오름차순으로 정렬한 뒤, 양의 정수 무게중 최솟값을 구해보자.
문제가 이해가 안가서 고생했다. 부분집합을 구해서 해볼까도 싶었다.
1부터 시작한다고 해보자. 거기에 추의 값을 더해서 그 값이 리스트의 다음 숫자보다 작으면 break해서 나오면 되고, 아니면 그 값을 더해주면 된다. 테스트 케이스를 몇 번 돌려보니까 이해가 갔다.
예를 들어 3/ 1 10 11을 넣는다고 해보자 그럼 당연히 2를 잴 수 없으니 정답은 2일 것이다.
예제를 보자 7 3 1 6 2 7 30 1 을 넣는다
이를 오름차순 정렬하면 1 1 2 3 6 7 30 이 된다. 1부터 가정하고 출발한다 1 < 1이 참이 아니니까, 1에 1을 더해주고 2가 된다 2 < 1이 참이 아니니까, 2에 1을 더해주고 3이 된다 3 < 2가 참이 아니니까, 3에 2를 더해주고 5가 된다 이렇게 7까지, 21이된 수를 출력하면 된다.
코드
import sys
T = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))
arr.sort()
target = 1
for i in range(T):
if(target < arr[i]):
break
target += arr[i]
print(target)
# list안에 공백 제거해서 문자열을 넣고 싶었다면,
# N = list(input().replace(" ", "")) # for문 돌지 않고 문자열 공백 제거해서, 리스트에 넣기