https://www.acmicpc.net/problem/22945
22945번: 팀 빌딩
능력치가 다 다른 개발자 $N$명이 팀 빌딩을 위해 한 줄로 서있다. 하나의 팀을 만들기 위해서는 개발자 2명이 반드시 모여야 한다. 개발자 A와 개발자 B가 팀을 만들 때 팀의 능력치는 아래와 같
www.acmicpc.net
생각보다 효율성을 맞추는 것이 굉장히 까다로웠던 문제.
O(N)으로 해결할 방법을 찾는 것이 핵심인 문제였다. (투포인터로 해결)
package BOJ.투포인터;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;
import java.util.function.Function;
public class BOJ_22945_팀빌딩 {
static Function<String, Integer> stoi = Integer::parseInt;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int ans = 0;
int n = stoi.apply(br.readLine());
int[] developers = new int[n];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
developers[i] = stoi.apply(st.nextToken());
}
int left = 0;
int right = n - 1;
while (left != right) {
ans = Math.max(ans, (right - left - 1) * Math.min(developers[left], developers[right]));
if (developers[left] < developers[right]) {
left++;
} else {
right--;
}
}
System.out.println(ans);
}
}
