[백준] 22945 팀빌딩

1. 문제

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

22945번: 팀 빌딩

2. 접근방법

거리 * 둘 중 작은 수의

가장 큰 값을 찾는 문제

 

먼저 가장 거리가 먼 0번인덱스와 마지막 인덱스 부터 계산을 해본다.

이후 거리를 1씩 줄여가는데 (둘 중 작은 수)가 더 크도록 해야하니

둘 중 작은 수의 인덱스를 한 칸 이동시킨다.

 

위 방식으로 진행하면 현재 거리로 선택할 수 있는 경우 중

가장 큰 (둘 중 작은 수)를 항상 선택할 수 있게 되므로 한번의 탐색으로 모든 경우 탐색이 가능하다.

 

1. 투포인터로 start = 0 ,end = N-1

2. 현재 위치의 계산 값으로 max 초기화

3. start와 end 위치 중 더 작은 값을 한칸 이동

4. start와 end위치가 역전 되면 종료

5. max 출력

 

 

 

3. 자바 코드

package Gold;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class G4_22945팀빌딩 {
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		int arr[] = new int[N];
		for(int i = 0 ; i < N ; i++)
			arr[i] = Integer.parseInt(st.nextToken());
		int start = 0;
		int end = N-1;
		int max = 0;
		while(start<end) {
			int calc = Math.min(arr[start],arr[end]) * (end - start - 1);
			max = Math.max(calc, max);
			if(arr[start] < arr[end])
				start++;
			else
				end--;
		}
		System.out.println(max);
	}

}

4. 마치며

투포인터 문제인 것을 알면 굉장히 쉬운데

문제 자체에서 투포인터라고 티를 엄청 내는 듯