문제
N개의 동전을 이용하여 만들 수 없는 양의 정수 금액 중 최솟값을 구한다.
입력
첫째 줄 -> N : 동전의 개수 (1 ~ 1,000)
둘째 줄 -> 동전의 화페 단위, N 개의 자연수 (1,000,000 이하)
출력
주어진 동전들로 만들 수 없는 양의 정수 금액 중 최솟값
풀이
1. 먼저 data를 정렬한다.
2. 처음에 금액 1을 만들 수 있는지 확인하기 위해 target=1로 설정한다.
3. 현재 data이 target을 만들 수 있으면 (data값<=target) target에 해당 data값을 더한 값이 다음 target이 된다.
4. data 값이 target보다 커서 더 이상 target을 증가시킬 수 없을 때까지 3을 반복한다.
n=int(input())
data=list(map(int,input().split()))
data.sort()
target=1
for x in data:
if x>target:
break
target+=x
print(target)
'algorithm > problems' 카테고리의 다른 글
프로그래머스 - 외벽 점검 (0) | 2021.01.13 |
---|---|
프로그래머스 - 자물쇠와 열쇠 (0) | 2021.01.13 |
프로그래머스 - 무지의 먹방 라이브 (0) | 2021.01.05 |
볼링공 고르기 (0) | 2021.01.05 |
백준 1439 - 뒤집기 (0) | 2021.01.05 |