18130번: 여름나기

먼저 \(N\)이 \(10\,000\)까지 들어오는 것을 보아서 각 선풍기마다 시간 간격만큼씩 더해가며 시뮬레이션 하는 풀이는 통과하기 힘들것이라는 짐작이 벌써 든다.

 

각 선풍기 마다 \(O(1)\)만에 가격을 구하는 풀이도 존재할 것 같지만, 일단은 쉽게 구현한다는 생각이 들어서 이분탐색을 떠올리게 된다.

 

대충 구상을 했으니 이제 코드를 짜기 시작한다.

 

라고 생각하고 코드를 짜다보니 시간이 이미 주어지므로 이분탐색이 전혀 필요 없다는 사실을 깨닫게 된다.

 

그렇다면 총 몇번을 추가 결제 해야 하는가를 구할 때 \(\displaystyle\left\lfloor\frac{Q}{K}\right\rfloor\)번인지 \(\displaystyle\left\lceil\frac{Q}{K}\right\rceil\)번인지 조금 헷갈릴 수 있다.

 

이럴 때는 보통 수를 직접 대입해보는 편이다. \(Q=7\)이고 \(K=3\)이면 \(2\)번 추가 결제를 하게 된다.

 

\(\displaystyle\left\lfloor\frac{Q}{K}\right\rfloor\)가 맞는 것 같다.

int rep = q / k;
int price = p + rep * (rep + 1) / 2 * c;

이렇게 코드를 작성하고 나니 어딘가가 벌써 불편하다. 바로 오버플로우가 날거 같은 느낌이 불길하다.

 

따라서 long long 으로 바꿔준 뒤 코드를 완성한 채로 제출을 해본다.

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
typedef long long ll;
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int n, q; cin >> n >> q;
	ll ansprice = INF; int ansidx;
	for (int i = 1; i <= n; i++) {
		int p, k, c; cin >> p >> k >> c;
		int rep = q / k;
		ll price = p + (ll)rep * (rep + 1) / 2 * c;
		if (price < ansprice) ansidx = i, ansprice = price;
	}
	cout << ansidx << " " << ansprice << '\n';
	return 0;
}

WA를 받았다.

 

문제를 다시 살펴보니 INF의 값이 \(2^{63}-1\) 이상이 돼야 할 것 같다.

 

다시 제출을 해보자.

WA를 받았다.

 

ansidx를 \(1\)로 초기화해야할것 같다.

다시 제출을 해보자.

WA를 받았다.

ll price = p + (__int128)rep * (rep + 1) / 2 * c;

오버플로우가 일어날 수 있으므로 고친 후 다시 제출을 했지만 WA를 받았다.

 

무언가 근본적인 문제가 있어 보인다.

 

\(\displaystyle\left\lfloor\frac{Q}{K}\right\rfloor\)가 아니라 \(\displaystyle\left\lfloor\frac{Q-1}{K}\right\rfloor\)가 맞는 것 같다.

 

도착하면 추가 결제를 할 필요가 없기 때문이다.

다시 제출을 했더니 AC를 받았다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int n, q; cin >> n >> q;
	ll ansprice = LONG_LONG_MAX; int ansidx = 1;
	for (int i = 1; i <= n; i++) {
		int p, k, c; cin >> p >> k >> c;
		int rep = (q - 1) / k;
		ll price = p + (__int128)rep * (rep + 1) / 2 * c;
		if (price < ansprice) ansidx = i, ansprice = price;
	}
	cout << ansidx << " " << ansprice << '\n';
	return 0;
}