[백준] 20366 - 같이 눈사람 만들래?

ㅇ[문제링크]

20366번: 같이 눈사람 만들래?

 

0. N 범위가 600이므로, O(N^3)까지 실행 가능하다

• O(N^2)로 엘사가 만들 수 있는 모든 눈사람 만들기
• O(N)으로 엘사의 눈사람에 가장 가까운 안나의 눈사람 찾기 (투 포인터 사용)

 

1. 두 눈덩이를 선택해 엘사의 눈사람을 만든다

• 크기가 큰 아래 눈덩이를 선택하고, 그 다음 위 눈덩이를 선택한다
• 이를 위해 입력값을 크기순으로 정렬해 사용

 

2. 엘사의 눈사람과 가장 가깝게 안나의 눈사람을 만든다

• 양쪽 끝 눈덩이(가장 큰/가장 작은)를 선택하면서 시작
• 안나의 눈사람이 더 크면 : 더 작아져야 한다 - 큰 눈덩이(위)를 한단계 더 작은 눈덩이로 교체
• 안나의 눈사람이 더 작으면 : 더 커져야한다 - 작은 눈덩이(아래)를 한단계 더 큰 눈덩이로 교체
• 두 눈사람의 크기가 같아지거나 / 안나의 눈사람의 위/아래 눈덩이가 교차하면 종료

 

3. 안나의 눈사람마다 갱신한 min값이 정답

 

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

public class Main{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = pint(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		int[]snow=new int[N];
		int min=Integer.MAX_VALUE;
		
		for (int i = 0; i < N; i++) {
			snow[i]=pint(st.nextToken());
		}
		
		Arrays.sort(snow);
		
		for (int elsaFst = 0; elsaFst < N; elsaFst++) {
			//아래쪽
			for (int elsaSnd = 0; elsaSnd < elsaFst; elsaSnd++) {
				//위쪽
				int elsaSnow = snow[elsaFst]+snow[elsaSnd];
				int fst=0,snd=N-1;
				
				//안나의 눈사람이 더 크면 - snd를 줄인다
				//더 작으면 - fst를 늘린다
				
				while(fst<snd) {
					if(fst==elsaFst || fst==elsaSnd) {
						fst++;continue;
					}

					if(snd==elsaFst || snd==elsaSnd) {
						snd--;continue;
					}
					
					int annaSnow = snow[fst]+snow[snd];
					min=Math.min( min, Math.abs(annaSnow-elsaSnow) );
					
					if(annaSnow>elsaSnow) {
						snd--;
					}
					if(annaSnow<elsaSnow) {
						fst++;
					}
					if(annaSnow==elsaSnow) {
						break;
					}
					
					
				}
				
			}
		}
		
		System.out.println(min);
		
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면