6-f 문제는 이해했는데 원래 작성한 코드가 왜 틀렸는지를 잘 모... - 인프런

인프런 커뮤니티 질문&답변

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

6-F

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

작성

283

틀린 코드

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;
}

c++코딩-테스트

답변 1

큰돌

지식공유자

안녕하세요 아이님 ㅎㅎ

일단.. 이거 코드가 안보입니다.

그래서 아이님 코드 일부분만 보고 제 코드에 이식을 시켜봤습니다.

#include<bits/stdc++.h>
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 << '\n'; 
	return 0;
}

이렇게 말이죠.

이걸 제출하면.

시간초과로 뜨는 것을 볼 수 있습니다.