1449 수리공 항승

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

1449번: 수리공 항승

 

int N = 4(구멍난 개수)

int M = 2 (테이프 길이)

hole[i] = 구멍난 곳 

 

원래 나는 

구멍난 곳(hole[i])이 정렬된 상태에서 

count = 4(구멍난 개수 ) 만큼 초기화 한 뒤

hole[i+1] <= hole[i]+M-1

이면,

테이프 하나로도 다음 구멍을 막을 수 있기 때문에

for문을 돌리며

그만큼 count수를 감소시키려고 했다.

 

(처음 구멍난 곳이 hole[i]일때, 하나의 테이프를 이용해서 그곳으로부터 M-1길이만큼 더 막을 수 있다)

 

그런데, 보니깐 문제가 있었다.

 

만약, 구멍난 곳이 1 2 3 6 7 8 9 10 11 12 13 이고 테이프 길이가 5라면 

1 2 3 (1개)

6 7 8 9 10 (1개)

11 12 13(1개) 

총 테이프가 3개 필요한데,

 

3에서 6으로 가는 사이도 M-1= 4 이내의 거리이기 때문에 count가 감소해서 필요한 테이프 수가 감소한다는 것이다.

 

그런데 사실, 1+M-1 = 1+4=5 라서,

1에서부터 시작된 테이프가 6을 막을 수가 없다.

그래서 이 경우 count가 줄어들면 안 되는데 내가 만든 코드에서는 줄어들게 된 것이다. 

 

그래서, 위의 경우와 같이

hole[i+1] <= hole[i]+M-1 

이 조건을 만족하는 모든 곳에

count수를 모두 감소시켜 준 다음에 

 

3,6 의 경우,

즉 1+4=5 보다 작은 값인 3에서

3+4=7 이내에 값이 있을 경우 즉 6

이 경우는 count를 1개 증가시켜주려고 했다. 

 

그런데 이것을 만드는 코드를 못 찾아서

나와 다른 풀이로 완성한 다른 사람의 코드를 참고했다.

 

완성 코드

 

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




public class Main {

	  public static void main(String[] args) throws IOException {

		  
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		  
		
		int result[] = new int [1001];
		
		StringTokenizer st1 = new StringTokenizer(br.readLine(), " ");
		
		int hole[] = new int [N];
		for(int i=0; i<N;i++) {
			hole[i] = Integer.parseInt(st1.nextToken());
		}
		
		for(int i=0;i<N;i++) {
			result[hole[i]] = 1;
		}
		
		int count=0;
		

		
		
		for(int i=1; i<=1000;i++) {
			if(result[i]!=0) {
			
				count++;
				i+=M-1;
			}
		}
		System.out.println(count);
	  }
		
		
}

 

 

 

구멍난 위치에서 오른쪽으로 M-1의 위치까지 또 다른 구멍들을 막을 수 있다.

 

 

맨마지막에 있는 for문에 대해 설명하자면,

일단, 예제에는 

4 2

1 2 100 101 

 

이 나와있으므로, 

hole[0]=1 hole[1]=2 hole[2]= 100 hole[3]=101 

이라서, 

result[1]=1 result[2]=1 result[100]=1 result[101]=1

인데, 

 

i=1 일때, result[1]!=0이므로,

count가 증가해서 1이 된다.

그리고, i=1+1=2가 된다.

 

그러면 다시 for문 처음으로 갔을 때, i=2차례가 아니라,

i=3차례가 된다.

 

그래서 구멍난 곳 2는 1에서부터 붙힌 테이프로 같이 막을 수 있게 된다.

 

i=3일 때 result[3]==0이므로,, i=100이 올 때까지 count는 1로 유지되고

i=100에서 count가 2로 증가함

 

 

참고 자료 :

https://zzang9ha.tistory.com/121

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