처음에는 MAX값을 변수로 두고, 최종 결과까지 가면서 남아있는 체력이 0 초과하기 위한 범위를 구하고 이 중 최솟값을 출력하는 방식으로 구현하려고 하였다. 사실 구현 양상을 보면 충분히 가능해보인다. 다만, 다른 방법으로는 가장 최악의 경우 몬스터가 엄청 쎄고 용사는 매우 약하다고 가정해보면 123456개의 방에서 몬스터의 공격력은 1000000이고, 체력도 1000000인데 용사의 공격력은 1이라고 하면 이 경우 최대 hp는 이 3개의 값을 곱한 값이다. 즉, HP는 1과 위의 최대 hp 사이에 존재할 수 밖에 없는 것을 활용해서 직접 다 계산해주면 된다. 최대 HP를 k라 하면 시간 복잡도는 O(nlgk)이므로 충분히 시간안에 돌아간다. #include #define fastio ios_base::..

사실상 백준 2792번 보석상자와 다른 부분이 하나도 없다. 물론 정렬하기는 해야한다는 점에서 차이가 아얘 없지는 않다. viyoung.tistory.com/186 [백준 2792번] [이분 탐색] 보석 상자 잘 생각해보면, 특정한 수를 나누고 몫과 나머지와 관련있다는 사실까지는 쉽게 파악할 수 있다. 다만, 해당하는 숫자를 판단하기 위해서 10e9 숫자를 판단해야하는데 이 부분은 이분탐색으로 해 viyoung.tistory.com 특정한 숫자 간격을 얼마만큼 형성할 수 있는지를 묻는 것이므로 근본적으로 나눗셈과 관련이 되어있다. 적당히 몫과 나머지를 보고 연산을 해주면 된다. 기존에 있는 주유소에는 다시 설치할 수 없으므로 나머지가 0인 경우에는 몫에서 - 1개만큼의 신규 주유소를 지을 수 있는 것이고..

잘 생각해보면, 특정한 수를 나누고 몫과 나머지와 관련있다는 사실까지는 쉽게 파악할 수 있다. 다만, 해당하는 숫자를 판단하기 위해서 10e9 숫자를 판단해야하는데 이 부분은 이분탐색으로 해결할 수 있음을 알 수 있다. 추가적으로 만족하는 상황 중에 가장 작은 숫자를 찾는 것이므로 lower_bound를 물어보는 것이다. 따라서 lower_bound binary search를 진행해주면 된다. #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; typedef long long ll; int main(void){ fastio; ll n, m; cin >> n >> m; vector ..

문제를 잘 보면 나눠줄 수 있는 "최대" 길이이므로 만족하는 숫자들의 범위 중 최댓값을 출력해주는 것이다. 따라서 이분탐색의 upper_bound를 활용해주면 된다. Upper_bound의 대략적인 skeleton code는 다음과 같다. // Upper_bound (이분탐색에서의 상계를 구하는 방법) int start = 0; int end = vector_container.size(); while (start M >> N; vector data_store; for(int i = 0; i > temp; data_store.push_back(temp); } sort(data_..