[G4] 백준 22945번 팀 빌딩 C++ 투 포인터

리뷰

 

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

신박한 투포인터 문제

 

 

전역 변수

• N : 배열의 최대 크기를 정의할 상수 변수
• t : 팀원들의 능력치를 저장할 배열
• n : 팀원의 수를 저장할 변수

 

함수

없음

 

 

문제풀이

1. n값을 입력 받고, n명의 개발자의 능력을 입력 받아 t배열을 초기화한다.
2. 변수 l을 0, r을 n-1로 초기화 하고, mx를 0으로 초기화한다.
3. l이 r미만일 경우를 조건으로 하는 while루프를 수행한다.
4. 매 루프마다 변수 le에 t[l]을, re에 t[r]을 저장하고, len을 r-l-1로 저장한다.
5. mx에 기존의 mx값과 len*min(le, re)와 비교해 더 큰 값을 저장한다.
6. le가 re보다 클 경우 r을 감소, 작을 경우 l을 증가, 같을 경우 r을 감소, l을 증가시킨다.
7. while루프가 종료된 후 mx에 저장된 값을 출력한다.

 

트러블 슈팅

1. len을 le-re-1로 초기화 하고 제출했더니 WA를 받았다.
2. 오타를 수정하여 len을 l-r-1로 초기화 하고 제출했더니 AC를 받았다.

 

참고 사항

1. 길이는 계속 줄어드므로 능력치가 작은 개발자의 포인터를 옮기는 방식으로 최적해를 찾을 수 있다.
2. 같은 경우엔 둘 다 포인터를 옮겨도 무방하다.

 

정답 코드

#include<iostream>
using namespace std;

const int N = 1e5;
int t[N];
int n;

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

	cin >> n;
	for (int i = 0; i < n; ++i) cin >> t[i];

	int l = 0, r = n - 1;
	int mx = 0;
	while (l < r) {
		int le = t[l], re = t[r];
		int len = r - l - 1;
		mx = max(mx, len * min(le, re));

		if (le > re) --r;
		else if (le < re) ++l;
		else {
			--r;
			++l;
		}
	}
	cout << mx;
}