https://www.acmicpc.net/problem/23978
효석이는 영일 코인을 매도해 K원 이상을 현금화하려고 한다. 효석이는 자신이 정한 N개의 날짜에 코인의 가격을 급상승시키고, 처음 코인의 가격이 오른 날부터 매일 한 개씩 매도할 계획이다. 효석이가 정한 날짜에 영일 코인은 X원으로 오르고, 그 후 0원이 될 때까지 하루에 1원씩 가격이 낮아진다. 코인의 가격이 너무 크게 오르면 의심을 살 수 있기 때문에 최소 금액으로 상승시켜 현금화를 하려고 한다. 마지막 가격 상승 이후 코인의 가격이 0이 될 때까지, K원 이상 현금화할 수 있는 가장 작은 정수 X를 구하는 문제다.
문제 탐색하기
- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정
ex. 가능한 시간 복잡도, 알고리즘 선택
입출력 제한
- 1 ≤ N ≤ 100,000
- 1 ≤ K ≤ 1,000,000,000,000,000,000
- 1 ≤ A_i ≤ 1,000,000,000
늘 풀던 매개 변수 탐색 문제와 비슷할 줄 알았지만, 시간 초과 결과를 보고 나서야 숫자 제한이 너무 크다는 걸 뒤늦게 알아챘다. K의 최댓값이 1e18이기 때문에 모든 변수를 long long int로 선언하는 게 좋다.
K의 최댓값이 1e18일 때, N이 1이고 첫 날부터 코인 가격을 올린 뒤 코인 가격이 그대로 쭉 떨어지는 상황을 생각해보면 K가 최댓값일 때의 X의 최솟값을 구할 수 있다.
- X부터 0까지의 합이 1e18보다 크거나 같아야 한다. ∴ (X+1) * X / 2 ≥ 1e18
- 위의 식을 풀면 X ≥ 1,414,213,562이다.
X의 최솟값은 1이므로 left를 1로 놓고, right는 X의 최댓값보다 적당히 크게(ex. 1e10) 설정해두면 long long int의 범위를 넘지 않게 이분 탐색을 진행할 수 있다.
i+1번째 코인이 오른 날짜에서 i번째 코인이 오른 날짜를 뺀 값(tmp)이 X보다 크거나 같으면, 코인 가격이 X에서 0까지 떨어지는 동안 코인 가격이 상승하지 않으므로 X에서 1까지 더한 값을 총합 변수에 저장하면 된다.
- N=2, A0=1, A1=5, X=2인 상황에서 코인 가격은 이렇게 나타낼 수 있다. → 2 1 0 0 2 1 0
- X에서 1까지 더한 값 = (2+1) × 2 / 2 = 3
tmp가 X보다 작은 경우엔 코인 가격이 X에서 0까지 떨어지기 전 중간에 코인 가격이 다시 X까지 상승하게 된다. tmp 동안 모든 날에 X원을 얻은 경우의 값에서 tmp-1부터 1까지 더한 값을 빼 총합 변수에 저장하면 된다.
- N=2, A0=1, A1=5, X=5인 상황에서 코인 가격은 이렇게 나타낼 수 있다. → 5 4 3 2 5 4 3 2 1
- tmp 동안 모든 날에 X원을 얻은 경우의 값 = 4 × 5 = 20
- tmp-1부터 1까지 더한 값 = (4-1) × 4 / 2 = 6
- 차이 = 14
총합 변수를 X부터 1까지 더한 값으로 초기화해두면 마지막으로 코인 가격이 오른 날부터 0원이 될 때까지의 값까지 포함할 수 있다.
코드 설계하기
위의 [문제 탐색하기]에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡고, 문제 풀이를 본격적으로 하기 전 이 문제를 풀기 위한 로드맵을 그리는 과정!
- 어떤 순서로 코드를 작성해야 할지
- 어떤 함수들을 작성해야 할지
- N, K, 날짜 정보 입력받기
- X의 값을 매개 변수로 놓고 이분탐색 진행하기
- l=1, r=1,500,000,000, ans=1,000,000,000,000,000,000으로 놓기
- n-1만큼 반복문을 돌면서 i+1번째 날짜와 i번째 날짜의 차이(=diff)가
- mid 이상이면, mid가 0이 될 때까지의 합을 더하기
- mid 미만이면, diff에 mid를 곱한 값에서 diff-1부터 0까지의 합을 빼기
- 얻은 돈이 K원
- 이상이면, r=mid-1로 놓고 ans 값 갱신하기
- 미만이면, l=mid+1로 놓기
- ans 값 출력하기
시도 회차 수정 사항 (Optional)
- '틀렸습니다'를 받았다면 왜 틀렸는지 고민해보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검
- 한 번에 맞히면 pass해도 됨!
1~3회차
- 시간초과
- 입력받는 A_i 값의 최댓값까지 반복문을 돌려 코인 가격을 더하면서 진행하려고 했음 → A_i의 최댓값이 1,000,000,000이라 연산 과정에서 시간 초과 발생
#include <iostream>
using namespace std;
long long int n,k,x,arr[1000001];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> k;
for (int i=0; i<n; i++) cin >> arr[i];
long long int l=0,r=k,ans=1e18;
while (l<=r) {
long long int mid=(l+r)/2,sum=0,pr=0,last=arr[n-1],idx=0;
for (int i=1; i<=last; i++) {
if (arr[idx]==i) {
pr = mid;
sum += pr;
idx++;
}
else {
if (pr>0) {
pr--;
sum += pr;
}
}
}
while (pr>0) {
pr--;
sum += pr;
}
if (sum>=k) {
r = mid-1;
ans = min(ans,mid);
}
else {
l = mid+1;
}
}
cout << ans;
}- mid 값에 따라 mid부터 0까지 더한 값을 저장하다보면 long long int의 범위를 벗어날 수 있음
- ex. l=0, r=1,000,000,000,000 → mid=500,000,000,000, max_sum>1e22
- 따라서 r 값을 적당한 값으로 조절해야 함
#include <iostream>
using namespace std;
long long int n,k,x,arr[1000001];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> k;
for (int i=0; i<n; i++) cin >> arr[i];
long long int l=0,r=k,ans=1e18;
while (l<=r) {
long long int mid=(l+r)/2,max_sum=(mid+1)*mid/2,sum=max_sum;
for (int i=0; i<n-1; i++) {
int tmp = arr[i+1]-arr[i], diff = mid-tmp;
sum += (tmp>=mid ? max_sum : max_sum - (diff+1)*diff/2);
}
if (sum>=k) {
r = mid-1;
ans = min(ans,mid);
}
else {
l = mid+1;
}
}
cout << ans;
}
정답 코드
#include <iostream>
using namespace std;
long long int n,k,x,arr[1000001];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> k;
for (int i=0; i<n; i++) cin >> arr[i];
long long int l=1,r=1500000000,ans=1e18;
while (l<=r) {
long long int mid=(l+r)/2,sum=(mid+1)*mid/2;
for (int i=0; i<n-1; i++) {
long long int tmp = arr[i+1]-arr[i], diff = min(mid,tmp);
sum += mid*diff - (diff-1)*diff/2;
}
if (sum>=k) {
r = mid-1;
ans = min(ans,mid);
}
else {
l = mid+1;
}
}
cout << ans;
}