[JS] Q04 만들 수 없는 금액

Hadam Cho·2021년 4월 4일

Algorithm

목록 보기

4/32

제한 사항

난이도	풀이 시간	시간 제한	메모리 제한
1	30분	1초	128MB

문제

동네 편의점의 주인인 동빈이는 N개의 동전을 가지고 있습니다. 이때 N개의 동전을 이용하여 만들 수 없는 양의 정수 금액 중 최솟값을 구하는 프로그램을 작성하세요.

예를 들어, N = 5이고, 각 동전이 각각 3원, 2원, 1원, 1원, 9원까지(화폐 단위) 동전이라고 가정합시다. 이때 동빈이가 만들 수 없는 양의 정수 금액 중 최솟값은 8원입니다.

또 다른 예시로, N = 3이고, 각 동전이 각각 3원, 5원, 7원짜리(화폐 단위) 동전이라고 가정합시다. 이때 동빈이가 만들 수 없는 양의 정수 금액 중 최솟값은 1원입니다.

입력 조건

첫째 줄에는 동전의 개수를 나타내는 양의 정수 N이 주어집니다. (1 ≤ N ≤ 1,000)
둘째 줄에는 각 동전의 화폐 단위를 나타내는 N개의 자연수가 주어지며, 각 자연수는 공백으로 구분합니다. 이때, 각 화폐 단위는 1,000,000 이하의 자연수입니다.

출력 조건

첫째 줄에 주어진 동전들로 만들 수 없는 양의 정수 금액 중 최솟값을 출력합니다.

입력 예시

5
3 2 1 1 9

출력 예시

8

소스 코드

function solution(N, data) {
  const n = Number(N);
  const numbers = data.split(' ').map(x => Number(x));
  numbers.sort((a, b) => a - b);

  let target = 1;
  for (let i = 0; i < numbers.length; i++) {
    if (target < numbers[i]) {
      break;
    }
    target += numbers[i];
  }

  console.log(target);
}

정답

n = int(input())
data = list(map(int, input().split()))
data.sort()

target = 1
for x in data:
  # 만들 수 없는 금액을 찾았을 때 반복 종료
  if target < x:
    break
  target += x

# 만들 수 없는 금액 출력
print(target)