6-f 문제는 이해했는데 원래 작성한 코드가 왜 틀렸는지를 잘 모르겠습니다.

Question

틀린 코드 https://www.acmicpc.net/source/58095478 문제는 이해를 했고 제가 짠 코드가 시간초과가 걸려야한다는 점도 이해했습니다. 처음 접근시 이분탐색 + check로 문제를 해결하려고 했는데요. 코드에서 naive하게 while문을 이용해서 몬스터의 체력을 공격력을 으로 빼주는 방법을 사용했고 용사가 먼저 때리고, 그다음 맞는 것도 구현했습니다. 이런 접근이 기존 시간 복잡도를 logN * N * (100000) 까지 증가할 수 있다는 점은 이해를 했는데, 왜 백준에서는 시간초과가 아닌 틀렸다고 나오는지 이해가 안되서 질문드립니다. 로직자체는 맞다고 생각이 드는데 시간초과도 틀리다고 뜰 수 있는걸까요? bool check(long long mid) { long long atk = hatk; long long hhp = mid; for (int i = 0; i < n; ++i) { if (v[i].t == 1) { mhp = v[i].h; matk = v[i].a; /* 왜 백준에서는 시간초과가 아니라 틀렸다고 나올까요? */ while (mhp > 0) { mhp -= atk; if (mhp <= 0) break; hhp -= matk; if (hhp <= 0) return false; } /* answer */ // long long div = mhp / atk + (mhp % atk ? 1 : 0); // long long cnt = div - 1; // hhp -= cnt * matk; } else { heal = v[i].h; addatk = v[i].a; atk += addatk; hhp = min(mid, hhp + heal); } /* answer */ // if (hhp <= 0) return false; } return true; }

큰돌 · Answer

안녕하세요 아이님 ㅎㅎ 일단.. 이거 코드가 안보입니다. 그래서 아이님 코드 일부분만 보고 제 코드에 이식을 시켜봤습니다. #include using namespace std; typedef long long ll; ll n, attack, t[130005], a[130005], h[130005], lo, hi, ret; void fastIO(){ ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); } bool check(long long mid) { long long atk = attack; long long hhp = mid; for (int i = 0; i < n; ++i) { if (t[i] == 1) { ll mhp = h[i]; ll matk = a[i]; while (mhp > 0) { mhp -= atk; if (mhp <= 0) break; hhp -= matk; if (hhp <= 0) return false; } } else { ll heal = h[i]; ll addatk = a[i]; atk += addatk; hhp = min(mid, hhp + heal); } } return true; } int main(){ fastIO(); cin >> n >> attack; for(int i = 0; i < n; i++){ cin >> t[i] >> a[i] >> h[i]; } lo = 1, hi = 1e18 + 4; while(lo <= hi){ ll mid = (lo + hi) / 2; if(check(mid)){ hi = mid - 1; ret = mid; }else lo = mid + 1; } cout << ret << ' '; return 0; } 이렇게 말이죠. 이걸 제출하면. 시간초과로 뜨는 것을 볼 수 있습니다. 아마 다른 로직 부분이 틀리신 것같아요. 저 check부분은 좀 느릴뿐이지 로직 자체는 깔끔하고 좋습니다. 로직자체는 맞다고 생각이 드는데 시간초과도 틀리다고 뜰 수 있는걸까요? >> 음 일단은 시간초과는 로직자체가 틀려서 무한루프 등이 생기거나 문제에서 주어진 시간타임라인에 못맞추면 시간초과가 뜹니다. 그리고 틀립니다는 엄연히 틀린 로직이 있어서 틀려요 ㅎㅎ 또 질문 있으시면 언제든지 질문 부탁드립니다. 좋은 수강평과 별점 5점은 제가 큰 힘이 됩니다. :) 감사합니다. 강사 큰돌 올림.