[G5] 백준 25603번 짱해커 이동식 C++ 매개변수 탐색

리뷰

 

https://www.acmicpc.net/problem/25603

회사 점심시간에 풀다가 틀렸는데 왜 자꾸 틀렸는지 고민했다가 집에 오자마자 맞췄다.

 

 

전역 변수

• N : 배열의 최대 크기를 정의할 상수 변수
• n : 기업 의뢰의 비용의 개수를 저장할 변수
• k : 스킵할 수 있는 비용의 최대 개수를 저장할 변수

 

함수

없음

 

 

문제풀이

1. n, k값을 입력 받고, 변수 mn을 0으로 초기화한다.
2. n개의 의뢰 비용을 입력 받아 arr배열을 초기화 하고, 그 중 최대값을 mn에 저장한다.
3. 변수 l을 1, r을 mn, ans를 mn으로 초기화한다.
4. l이 r이하일 경우를 조건으로 하는 while루프를 수행한다.
5. 변수 mid를 (l+r)을 2로 나눈 몫으로 저장하고, cnt를 0으로 초기화한다.
6. arr을 순회하며, 현재 값이 mid보다 클 경우 cnt를 증가시키고, 아니라면 cnt를 0으로 변경한다.
7. 만약 cnt가 k이상이 될 경우 더 이상 탐색할 필요가 없으므로 break처리한다.
8. 최종적으로 cnt가 k이상일 경우 l을 mid+1로 저장하고, 아니라면 r을 mid-1로, ans를 mid로 저장한다.
9. while루프가 종료된 후 ans에 저장된 값을 출력한다.

 

트러블 슈팅

1. while루프의 범위를 l이 r보다 작을 경우로만 체크해주어 WA를 받았다.
2. l이 r과 동일할 때에도 루프를 타게 로직을 변경해주어 AC를 받았다.

 

참고 사항

1. K는 N보다 작으며, N은 최대 10만이고, 각 비용은 최대 1억까지 주어지므로 int범위 내로 해결할 수 있다.

 

정답 코드

#include <iostream>
using namespace std;

const int N = 1e5;
int n, k;
int arr[ N ];

int main()
{
	ios::sync_with_stdio( 0 );
	cin.tie( 0 );
	cout.tie( 0 );

	cin >> n >> k;
	int mn = 0;
	for ( int i = 0; i < n; ++i )
	{
		cin >> arr[ i ];
		mn = max( mn, arr[ i ] );
	}

	int l = 1, r = mn, ans = mn;
	while ( l <= r )
	{
		int mid = ( l + r ) / 2;
		int cnt = 0;
		//cout << mid << " ";

		for ( int i = 0; i < n; ++i )
		{
			if ( arr[ i ] > mid )
				++cnt;
			else
				cnt = 0;

			if ( cnt >= k ) break;
		}

		//cout << cnt << "\n";

		if ( cnt >= k )
		{
			l = mid + 1;
		}
		else
		{
			r = mid - 1;
			ans = mid;
		}
	}
	cout << ans;
}