인프런 커뮤니티 질문&답변
작성한 질문수
백준 16434 문제
작성
·
292
0
http://boj.kr/904d5fdfb1014610bca4d8d8b46ad8b5
저는 일단 생각한게 매번 방마다 필요한 체력을 구할 때
(용사가 드래곤을 죽이기 위해 때리는 횟수-1) x 드래곤의 공격력 = 필요한 체력 이라는 공식을 세웠고,
n이 최대 백만개이니깐 최소 nlogn으로 구하기 위해서 매번 방마다 용사가 드래곤을 죽이기 위해 때리는 횟수를 이분탐색을 이용해서 구한 뒤
포션방을 들어갔을 때, ans을 갱신하고 그 포션의 체력과 현재 필요한 체력을 비교해서 sum(필요한 체력)을 두가지 경우로 나눠서 ( 포션이 필요한 체력보다 크다면 sum=0으로 갱신, 포션이 필요한 체력보다 작다면
sum=필요한 체력 - 포션) 으로 갱신하고 다음 방으로 들어가는 알고리즘을 짰습니다.
문제나 질문 게시판에 있는 반례들은 다 돌아가는데 채점을 하면 2퍼센트에서 터집니다. 무엇이 문제일까요?...
답변 1
0
질문게시판에 있는 반례들을 다 하셨다고 하길래 수만km를 거쳐 반례를 찾아왔습니다.(제가 생각한 겁니당~)
감사합니다.
그게 아니죠. 이 코드 자체가 초기 공격력이 넘쳤을 때를 대응을 못하는 거잖아요. 디버깅을 해보면 mid가 이상하게 가는 걸 볼 수가 있어요.
#include<bits/stdc++.h>
using namespace std;
int n, atk;
long long ans = 0;
vector<tuple<int, int, int>> v;
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> atk;
for (int i = 0; i < n; i++) {
int a, b, c;
cin >> a >> b >> c;
v.push_back({ a,b,c });
}
long long sum = 0;
for(int i=0;i<n;i++){
int info, atk1, h; // 정보 , 공격력 ,체력
tie(info, atk1, h) = v[i];
if (info == 1) {
long long l = 0, r = 1e18+4, mid;
long long cnt = 1e18+4;
while (l <= r) {
mid = (l + r) >> 1;
if (mid * atk >= h) {
cnt = min(cnt, mid);
r = mid - 1;
}
else l = mid + 1;
cout << mid << '\n';
}
sum += (cnt - 1) * atk1;
//if (i == n - 1) sum++;
}
else {
//sum++;
if (ans < sum+1) ans = sum + 1;
if (sum > h) sum -= h;
else sum = 0;
atk += atk1;
}
//cout << sum << endl;
}
if (ans < sum+1) ans = sum + 1;
cout << ans;
}
/*
1 100 1 1 1
500000000000000000
750000000000000000
625000000000000000
*/
r의 값을 1e13으로 줄이면 mid가 감소하면서 1로 나옵니다! r을 1e18로 크게 잡다보니 mid x (용사 공격력) 이 long long 범위를 초과해서 이상하게 나온거 같은데.. 맞는지는 모르겠습니다
원래 그냥 몇번을 때릴지 구하려면 for문 한번으로 구하면 O(n)인데 그럼 n^2으로 시간초과가 나서 이걸 logn에 구하기 위해서 이분탐색을 썻습니다.
네 long long 을 초과해서 그렇게 되는 거구요. 1,000,000이 용사의 최대 초기공격력이라 이 코드가지고는 long long 범위를 무조건 초과해서 안 될 것같아요.
감사합니다.. 이 문제는 long long 범위를 초과해서 나타난 문제였네요.. INF 범위를 줄여서 다시 제출했는데 2퍼에서 여전히 터지네요.. 이 문제가 아닌가 봅니다ㅠㅠ