문제 79
종이의 집
세종대학교에는 금고가 $N$개 존재한다. 종이는 금고를 털려고 한다!
금고를 너무 많이 털면 들킬 수 있기 때문에 최대 $2$개의 금고만 털려고 한다!
각 금고에 들어있는 금액이 주어지면 털 수 있는 금액의 최댓값을 출력하라.
입력
첫 번째 줄에 정수 $N$이 주어진다. $(2 \le N \le 100)$
두 번째 줄에 각 금고에 들어 있는 금액을 의미하는 $N$개의 정수 $x_1, x_2, \cdots, x_N$이 공백으로 구분되어 주어진다. $(0 \le x_i \le 500)$
출력
첫 번째 줄에 털 수 있는 금액의 최댓값을 출력한다.
예제 입력 1
3 9 2 3
예제 출력 1
12
예제 입력 2
4 5 2 4 5
예제 출력 2
10
공식 해설
금액이 모두 음수가 아니고 금고가 적어도 두 개 있으므로, 금고를 두 개 선택해도 하나만 선택할 때보다 나빠지지 않는다. 선택한 금고보다 돈이 많은 다른 금고가 있다면 바꾸는 것이 유리하므로 가장 큰 두 금액의 합이 답이다.
전체를 정렬할 필요 없이 지금까지의 가장 큰 값과 두 번째로 큰 값만 유지한다. 새 금액이 최댓값보다 크면 기존 최댓값을 두 번째로 옮기고 최댓값을 바꾼다. 그렇지 않으면 두 번째 값과 비교하여 갱신한다.
두 값을 $0$으로 시작하면 금액이 모두 $0$이어도 처리된다. 같은 금액의 금고도 서로 다른 금고이므로 최댓값과 같은 금액이 다시 나오면 두 번째 값에 들어갈 수 있어야 한다.
시간복잡도는 $O(N)$, 추가 공간복잡도는 $O(1)$이다.
구현 · 언어별 풀이
C++ 구현
가장 큰 두 값을 담는 int 변수 두 개를 $0$으로 초기화한다. 새 값이 첫 번째 값보다 크면 기존 첫 번째를 두 번째로 옮기고, 그렇지 않으면 두 번째와 비교한다. 같은 최댓값이 두 번 들어올 때도 두 금고를 모두 셀 수 있어야 한다.
C 구현
최댓값 두 개를 int 변수로 유지한다. 같은 값도 서로 다른 금고라면 두 번 선택할 수 있으므로 중복을 제외하지 않는다. 합의 최댓값은 1000이라 int로 충분하다.
Python 구현
최댓값과 두 번째 값을 변수로 갱신하거나 정렬 뒤 마지막 두 값을 더한다. set으로 만들면 값이 같은 두 금고를 잃는다. 금고 번호의 서로 다름과 금액의 서로 다름을 혼동하지 않는다.
Java 구현
두 최댓값은 int로 유지한다. 입력 금액이 0 이상이라 초기값 0을 사용할 수 있고 동일한 최대 금액도 둘 다 반영한다. 별도 heap이나 금고 객체는 필요 없다.
Rust 구현
두 최대 금액을 i32 변수로 갱신한다. 같은 금액도 두 위치면 모두 사용할 수 있다. 답이 1000 이하이므로 i64나 u128을 사용할 이유는 없다.
JavaScript 구현
가장 큰 금액 두 개를 Number 변수에 유지한다. 모든 금액이 $0$ 이상이므로 초기값을 둘 다 $0$으로 둘 수 있다. 새 값이 최댓값 이상이면 기존 최댓값을 두 번째로 넘긴다.
let first = 0, second = 0;
for (const x of amounts) {
if (x >= first) {
second = first;
first = x;
} else if (x > second) {
second = x;
}
}
console.log(first + second);같은 금액의 서로 다른 금고도 두 개 고를 수 있으므로 Set으로 중복을 제거하지 않는다. 합은 $1\,000$ 이하이며 BigInt나 우선순위 큐는 필요 없다.