취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 24379번 문제인 КИФЛИЧКИ이다.

문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/24379 

문제의 상황을 우리말로 서술하면 다음과 같다.

BOJ 24379: 소라빵

문제)
꼬마 피터는 소라빵을 좋아합니다. 피터가 다니는 학교의 매점에서는 세 가지 종류의 내용물(마멀레이드, 초콜릿, 크림)이 각각 들어있는 세 종류의 소라빵을 판매합니다. 피터는 매우 배가 고파 살 수 있는 가장 많은 개수의 소라빵을 사려고 합니다. 하지만 매점에 남아있는 소라빵의 개수나 피터의 돈은 무한하지 않습니다.
피터가 최대한 많은 소라빵을 살 수 있게끔 프로그램을 작성해 도와주세요.

입력)
입력은 세 줄로 이루어져 있습니다.
첫 번째 줄에는 세 개의 정수가 사이에 공백을 두고 주어집니다. 각 정수는 순서대로 마멀레이드 소라빵, 초콜릿 소라빵, 크림 소라빵의 가격을 의미합니다.
두 번째 줄에는 세 개의 정수가 사이에 공백을 두고 주어집니다. 각 정수는 순서대로 매점에 남아있는 마멀레이드 소라빵, 초콜릿 소라빵, 크림 소라빵의 수량을 의미합니다.
세 번째 줄에는 피터가 가지고 있는 돈을 나타내는 하나의 정수가 주어집니다.

출력)
한 줄에 피터가 살 수 있는 소라빵의 개수의 최댓값을 출력합니다.

제한)
입력으로 주어지는 모든 정수는 1,000,000,000,000,000,000 보다 작은 음이 아닌 정수입니다.

문제 제한에서 입력으로 0이 들어올 수 있다는 점을 확인하자.

가장 저렴한 소라빵서부터 살 수 있는 대로 전부 사는 것을 반복하는 것으로 문제를 해결할 수 있다.

문제의 입력으로 들어오는 수의 크기가 매우 크므로, 입력된 두 수를 곱할 때 64비트 정수형으로 표현한 범위를 넘는 경우가 많이 생길 수 있다. 그런 경우 gcc에서 지원하는 자료형인 __int128을 이용하면 편리하게 구현이 가능하다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef __int128 int128;
pair<ll, ll> arr[3];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	for (int i = 0; i < 3; i++) cin >> arr[i].first;
	for (int i = 0; i < 3; i++) cin >> arr[i].second;
	sort(arr, arr + 3);
	ll money; cin >> money;

	ll ans = 0;
	for (int i = 0; i < 3; i++) {
		if ((int128)arr[i].first * (int128)arr[i].second <= (int128)money) {
			money -= arr[i].first * arr[i].second;
			ans += arr[i].second;
		}
		else { // arr[i].first > 0
			ll cnt = money / arr[i].first;
			money -= arr[i].first * cnt;
			ans += cnt;
		}
	}

	cout << ans;
}