제한 조건
- 풀이 시간 : 30분
- 시간 제한 : 1초
문제
동네 편의점의 주인인 동빈이는 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 |
| 3 5 6 7 | 1 |
풀이
이 문제를 풀기 위해서는 먼저 숫자의 최소값, 중복 또는 연속성을 파악하기 위해 정렬을 해야 한다.
기본적으로 1보다 큰 숫자가 최소값이면 1은 절대 만들 수 없다. 그래서 이 경우를 제외하면 나머지는 무조건 1부터 시작한다고 생각해야 한다. 그리고 1부터 시작하여 중복되거나 연속된 숫자까지의 합까지는 모두 만들어질 수 있다.
이제 연속되지 않은 숫자들은 어떻게 처리할 것인지가 관건이다. 우선 숫자들을 늘어놓고 보면 쉽게 파악할 수 있다. 1 2 3 7이란 숫자들이 있다고 가정해보자.
1 2 3 4 5 6 -> 1 2 3으로 만들 수 있는 숫자 조합
(+7) 8 9 10 11 12 13 -> 위 조합에서 7을 더해 만들 수 있는 숫자 조합이렇게 조합해보면 1부터 13까지 모두 만들어질 수 있다는 것을 확인할 수 있다.
그렇다면 1 2 3 9란 숫자이 있을 경우를 확인해보자.
1 2 3 4 5 6 -> 1 2 3으로 만들 수 있는 숫자 조합
(+9) 10 11 12 13 14 15 -> 위 조합에서 9를 더해 만들 수 있는 숫자 조합이 경우에는 7, 8이 만들어질 수 없는 숫자라는 것을 확인할 수 있다.
이 과정을 통해서 (연속된 숫자들의 합 + 1) > 연속되지 않은 숫자일 경우에는 연속된 숫자들의 합과 연속되지 않은 숫자 사이의 숫자를 만들 수 없다는 것을 확인할 수 있다.
마지막으로 1부터 연속되지 않은 숫자들 중에 중복이 있다해도 원리는 동일하게 적용이 가능하다. 1 2 3 7 7이 있을 경우
1 2 3 4 5 6 -> 1 2 3으로 만들 수 있는 숫자 조합
(+7) 8 9 10 11 12 13 -> 위 조합에서 7을 더해 만들 수 있는 숫자 조합
(+7) 14 15 16 17 18 19 20 -> 위 조합에서 7을 더해 만들 수 있는 숫자 조합총합까지의 숫자가 모두 조합될 수 있다는 것을 확인할 수 있다.
결국 1부터 연속되지 않은 숫자들은 (이전 숫자들의 총합 + 1) > 연속되지 않은 숫자를 충족하는지 확인하면 된다.
이 내용을 간단하게 정리하면 다음과 같다.
- 최소값이 1보다 크면 1을 반환
- 중복 포함 연속된 숫자의 최대값까지의 합 구하기
- 다음 숫자가 (2번 결과 + 1)보다 크면 (2번 결과 + 1) 반환
- 다음 숫자가 (2번 결과 + 3번 숫자 + 1)보다 크면 (2번 결과 + 3번 숫자 + 1) 반환
- 4번 반복하다가 숫자가 더 없다면 (모든 숫자 총합 + 1) 반환
이 문제를 풀이하기 위해 필요한 자료구조는 List다.
풀이에 사용된 알고리즘의 시간 복잡도는 정렬을 위한 O(NlogN)과 각 숫자들을 꺼내와 처리하기 위한 O(N)가 있다. 결과적으로 O(NlogN)의 시간 복잡도를 가지며, 동전의 개수가 1,000개이므로 풀이가 가능하다.
이슈
이 문제를 제한 시간보다 10분 정도 초과해서 풀었다. 조금 힌트를 얻자마자 확인해야 할 케이스들을 충분히 검증하지 않고 논리 흐름을 완성하려고 하다보니, 중간에 놓친 케이스들이 떠올라 다시 확인하고 논리흐름을 다시 작성하는 과정을 반복하다가 늦어졌다.
조금 더 생각을 차분히 정리하고 논리흐름을 완성할 필요가 있다.
하지만 성급하게 코드를 작성하지 않고, 논리흐름을 먼저 완성하려한 점은 긍정적이라고 볼 수 있을 것 같다.
코드
