백준 34734 (C++) Coatless in Yakutsk

최초 업로드: 2025-11-14 14:36:12

최근 수정 시간: 2025-11-14 14:36:12

게시자: rlatjwls3333

카테고리: 백준

# [Silver III] Coatless in Yakutsk

[문제 링크](https://www.acmicpc.net/problem/34734)

## 문제 설명

It was your first time visiting Salvador, and you made the rookie mistake of sleeping on the beach. You woke up red, sunburned, and frankly, humiliated. Swearing vengeance against the sun and all its terrible consequences, you decided that your next vacation would be somewhere with a real winter – like Yakutsk, Russia, where the average temperature is $−42^\circ$ Celsius.

But you came prepared! You brought a warm, cozy coat. The coat is perfect, it warms you very well. Maybe too well, as you get sweaty and the coat gets dirty after $C$ days of use. Since your trip lasts more than $C$ days, you must find a way to avoid walking around smelling bad.

To do so, when the coat gets dirty, you cannot wear it until it is washed, but you may also choose to wash it earlier. On any day you do not wear the coat – whether because it is dirty or being washed – you must endure the day’s temperature without its protection. After being washed, the coat is fresh and ready to be worn again. At the start of your trip, the coat is clean.

Given the daily temperatures in Yakutsk for the duration of your trip, you must determine the lowest temperature on a day when you are forced to be without your coat, assuming you schedule wash days optimally to make this temperature as high as possible.

## 입력

The first line contains two integers $C$ and $N$ ($1 ≤ C < N ≤ 10^5$), indicating respectively the number of days you can wear the coat before it gets dirty, and the duration in days of your holidays.

The second line contains $N$ integers $T_1, T_2, \dots , T_N$ ($−50 ≤ T_i ≤ 50$ for $i = 1, 2, \dots , N$), where $T_i$ is the temperature on the $i$-th day.

## 출력

Output a single line with an integer indicating the minimum temperature you must endure without your coat.

## 풀이
빨래를 할 최소 온도를 설정하여, 그 온도 이상일 때만 빨래를 하는 방식으로 이 온도에서 적절한지 판단할 수 있다. 온도의 범위가 컸으면 이분 탐색을 섞어 풀 수 있다.

``` c++
#include<bits/stdc++.h>
using namespace std;

int c, n, t[100'000];

bool chk(int i) {
 int cnt=0;
 for(int j=0;j<n;j++) {
 if(t[j]<i) cnt++;
 else cnt=0;
 if(cnt>c) return false;
 }
 return true;
}

int main() {
 ios::sync_with_stdio(0); cin.tie(0);
 cin >> c >> n;
 for(int i=0;i<n;i++) cin >> t[i];

for(int i=50;i>=-50;i--) {
 if(chk(i)) {
 cout << i;
 return 0;
 }
 }
}
```