문제 소개
세 개의 정수 n, a, b가 주어진다고 가정해 봅시다. 우리는 정확히 n리터의 물을 구매하려고 하며, 근처에서 판매하는 물병은 두 종류뿐입니다. 첫 번째 종류는 1리터 병으로 가격이 a루피이고, 두 번째 종류는 2리터 병으로 가격이 b루피입니다. 목표는 가능한 한 적은 돈을 지출하여 정확히 n리터의 물을 구매하는 것이며, 이때 지불해야 하는 최소 금액을 구하는 것이 이 문제의 핵심입니다.
예를 들어, 입력이 n = 7, a = 3, b = 2라고 해보겠습니다. 이 경우 출력은 9가 됩니다. 2리터 병 3개를 구매하면 6리터의 물을 6루피에 확보할 수 있고, 남은 1리터는 1리터 병 하나를 3루피에 구매하여 채우기 때문입니다.
해결 접근 방법
이 문제는 그리디(Greedy) 방식으로 간단하게 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
먼저 2리터 병의 실질적인 가성비를 판단해야 합니다. 만약 1리터 병 두 개의 가격(a × 2)이 2리터 병의 가격(b)보다 저렴하다면, 굳이 2리터 병을 살 필요가 없습니다. 따라서 b의 값을 min(a × 2, b)로 갱신하여 항상 더 유리한 선택을 반영합니다. 그런 다음 n ÷ 2개의 2리터 병을 구매하고, n이 홀수일 경우 남은 1리터는 1리터 병 하나로 채웁니다.
이를 의사 코드로 표현하면 다음과 같습니다.
b := min(a * 2, b) return (n / 2) * b + (n mod 2) * a
C++ 구현 예제
아래 구현을 통해 더 자세히 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
int solve(int n, int a, int b) {
b = min(a * 2, b);
return n / 2 * b + n % 2 * a;
}
int main() {
int n = 7;
int a = 3;
int b = 2;
cout << solve(n, a, b) << endl;
}입력
7, 3, 2
출력
9
복잡도 분석
시간 복잡도: O(1) — 단순한 산술 연산만 수행하므로 입력 크기와 무관하게 일정한 시간이 걸립니다.
공간 복잡도: O(1) — 추가 메모리를 거의 사용하지 않습니다.