[백준] 1449번: 수리공 항승(그리디, 정렬)

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

1449번: 수리공 항승

틀린 코드

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());
		int N = Integer.parseInt(st.nextToken());	// 물이 새는 곳의 개수
		int L = Integer.parseInt(st.nextToken());	// 테이프 길이
		int min = 0;	// 필요한 테이프의 최소 개수
		int[] arr = new int[N];
		st = new StringTokenizer(bf.readLine());
		for(int i=0; i<arr.length; i++) {
			arr[i] = Integer.parseInt(st.nextToken()); 
		}
		
		Arrays.sort(arr);
		for(int i=0; i<arr.length-1; i++) {
			/*
			 * 물이 새는 두 곳의 위치 차이가 테이프-1의 길이와 동일하다면 ?
			 * L = 2이고, 물이 새는 두 위치가 1, 2 일때
			 * 0.5 | 1 | 1.5 | 2 | 2.5 (0.5 ~ 2.5 = 2 = L)
			 * 위와 같이 물이 새는 두 곳을 테이프 하나로 막을 수 있다.
			 * 따라서 테이프 +1 , 물이 새는 위치 하나 건너뛰기
			 */
			if(arr[i+1] - arr[i] == (L-1)) {
				min ++;
				i ++;
			}
			else {
				min ++;
			}
		}
		System.out.println(min);
		bf.close();
	}

}

이해

그리디 문제는 문제 이해하기가 젤 우선인 것 같다... 처음 문제를 봤을때 이해가 안돼서 읽어보고 읽어보다... 읽으니 이해를 할 수 있었는데, 문제는 다음과 같다.

● 물이 새는 곳의 개수(N)과 테이프의 길이(L)이 주어지는데, 물이 새는곳을 막고, 테이프를 최소한 사용하라.

●물이 새는곳은 그 위치의 좌우 0.5만큼의 간격을 줘야 물이 다시는 안샌다고 한다.

문제에 주어진 예제 입력

4 2 

1 2 100 101

을 토대로 그려보면 다음과 같다.

발그림 죄송

1의 좌우 0.5만큼(0.5 , 1.5) 와 2의 좌우 0.5만큼(1.5 , 2.5)간격을 주고 테이프를 붙여야하는데, 1과 2는 사이에 중복이되고, 테이프의 길이는 2이므로 물이 새는곳은 1, 2 두곤데지만 테이프 한개로 해결할 수 있다.

100과 101도 마찬가지다.

 

따라서 문제대로 두 배열의 요솟값의 차이와 테이프-1 만큼의 길이가 같을경우는 테이프 1개로 막고, 다음 인덱스로 넘어가면 된다고 생각했지만, 반례가 존재한다.

 

물이 새는곳의 개수는 5이고, 길이가 2이고, 물이 새는곳이 4, 5, 6, 7, 8 일때를 생각해보자.

물이 새는 곳이 4일때, 테이프를 하나 막으면 3.5 ~ 5.5까지 막을 수 있다.

그 후 6이 아닌 7에서 막으면, 6.5 ~ 8.5까지 막을 수 있다. 

즉, 테이프 2개로 다 해결할 수 있는데 위 코드라면 테이프가 3개가 필요하다.

 

그래서 접근을 다르게 해봤다.

 

정답 코드

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());
		int N = Integer.parseInt(st.nextToken());	// 물이 새는 곳의 개수
		int L = Integer.parseInt(st.nextToken());	// 테이프 길이
		int min = 0;	// 필요한 테이프의 최소 개수
		int[] arr = new int[N];
		st = new StringTokenizer(bf.readLine());
		for(int i=0; i<arr.length; i++) 
			arr[i] = Integer.parseInt(st.nextToken()); 

		//현재 물이 샌곳에 테이프를 붙였을때, 테이프가 영향을 미치는 범위
		int tapeRange = (int)(arr[0] - 0.5 + L);
		min ++;

        Arrays.sort(arr);

		for(int i=1; i<arr.length; i++) {
			if (tapeRange < (int)(arr[i] + 0.5)){
				tapeRange = (int)(arr[i] - 0.5 + L);
				min ++;
			}
		}

		System.out.println(min);
		bf.close();
	}

}

풀이

기지국설치문제 보기

저번에 프로그래머스에서 푼 기지국 설치하는 문제와 로직이 거의 동일(?) 한 것 같다. 그리디하게 접근하면 된다.

가장 앞 쪽부터 먼저 테이프를 하나 막고, 만약 다음 물이 새는 곳이, 이전에 테이프를 막은 범위 이내라면

테이프를 설치하지 않고 넘어간다.

만약 다음 물이 새는 곳이 이전 테이프를 막은 곳의 범위를 벗어 날 경우 => if (tapeRange < (int)(arr[i] + 0.5))

 

 -> 테이프의 범위를 다시 지정하고, 테이프를 +1 해준다.

발그림 죄송

위에 제시한 그림처럼 만약 1번 위치에 테이프를 설치할 경우 ? 

0.5 ~ 2.5까지 범위이므로, arr[i] - 0.5 + L 이라는 범위가 나온다.

 

* 가장 첫 배열의 요소에는 반드시 테이프를 설치해야 하므로, 초기 테이프의 범위는 배열 인덱스의 0번째에 테이프를 설치할 경우를 범위로 지정한다.

* 입력에서 오름차순으로 입력받는것이 아니므로, 배열을 입력한 후 정렬을 해주어야 한다.

 

다른 풀이

import java.io.*;
import java.util.*;
public class Main {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] t = br.readLine().split(" ");
		int  N = Integer.parseInt(t[0]);
		int  L = Integer.parseInt(t[1]);
		int pos[] = new int[1001];
		int tape=0;
		String[] input = br.readLine().split(" ");
		for(int i=0; i<N; i++) {
			pos[Integer.parseInt(input[i])] = 1;
		}


		for(int i=1;i<=1000;i++) {
			if(pos[i]!= 0) {
				i+=L-1;
				tape++;
			}
		}

		System.out.println(tape);
	}

}

배열의 인덱스를 통해 해결한 풀이 ...