문제 설명
n개의 요소를 가진 coins라는 배열이 있다고 가정해 보겠습니다. 이 배열은 우리가 소유한 동전들을 나타내며, i번째 동전의 가치는 coins[i]로 표현됩니다. n개의 동전 중 일부를 선택했을 때 그 합이 x가 된다면, 우리는 값 x를 만들 수 있습니다. 이 문제에서는 0부터 시작하여 연속적으로 만들 수 있는 값의 최대 개수를 구해야 합니다.
예를 들어, 입력이 coins = [1,1,3,4]라면 출력은 10이 됩니다. 그 이유는 다음과 같습니다:
- 0 = []
- 1 = [1]
- 2 = [1,1]
- 3 = [3]
- 4 = [4]
- 5 = [4,1]
- 6 = [4,1,1]
- 7 = [4,3]
- 8 = [4,3,1]
- 9 = [4,3,1,1]
0부터 9까지 총 10개의 값을 모두 만들 수 있지만, 10은 어떤 조합으로도 만들 수 없으므로 정답은 10입니다.
풀이 방법
이 문제는 그리디(Greedy) 알고리즘을 사용하면 효율적으로 해결할 수 있습니다. 해결 단계는 다음과 같습니다:
- coins 리스트를 오름차순으로 정렬합니다.
- ans를 1로 초기화합니다. (현재까지 0부터 ans-1까지의 모든 값을 만들 수 있음을 의미)
- coins의 각 동전에 대해 다음을 반복합니다:
- 만약 coin > ans라면, ans라는 값을 만들 수 없으므로 반복문을 종료합니다.
- 그렇지 않으면 ans에 coin을 더합니다. (만들 수 있는 범위가 ans + coin - 1까지 확장됨)
- ans를 반환합니다.
핵심 아이디어는 다음과 같습니다. 현재 ans까지의 모든 값을 만들 수 있는 상태에서 새로운 동전 c를 추가하면, c부터 c+ans-1까지의 값도 추가로 만들 수 있게 되어 범위가 ans+c까지 확장됩니다. 단, 동전의 가치가 ans보다 크면 ans 자체를 만들 방법이 없으므로 탐색을 중단합니다.
예제 코드
다음 파이썬 구현을 통해 더 잘 이해할 수 있습니다:
def solve(coins): coins.sort() ans = 1 for coin in coins: if coin > ans: break ans += coin return ans coins = [1,1,3,4] print(solve(coins))
입력
[1,1,3,4]
출력
10
시간 및 공간 복잡도
배열 정렬에 O(n log n), 순회에 O(n)의 시간이 소요되므로 전체 시간 복잡도는 O(n log n)입니다. 입력 배열을 제자리(in-place) 정렬하는 경우 공간 복잡도는 O(1)입니다.