[BOJ 1449] 수리공 항승 - JAVA

수리공 항승 / 그리디 문제를 풀어보았습니다

 

어렵게 생각하지 않고 몇 번의 조건절을 추가 한다면 쉽게 풀리는 문제였습니다.

하지만 어렵게 생각해버린 나..ㅋㅋ

 

이제 구현 내용을 보도록 하겠습니다.

이 방법은 개인적인 방법이며 최적의 솔루션이 아닐 수 있습니다.

 

구현 내용

 

구현 방법

가장 중요한 것은 조건절을 잘 생각하면 됩니다.

 

1. L보다 물 새는 곳의 위치의 차이가 작다면 다음 칸을 확인합니다. 물 새는 곳의 위치의 차이 +1(양쪽으로 0.5씩 더 붙혀야하기 때문에) 값이 L과 같다면 테이프를 붙히고 붙힌 곳은 더 이상 확인을 하지 않습니다.

2. 만약 L보다 물 새는 곳의 위치의 차이가 같거나 크다면 여러개의 테이프를 붙혀야하기 때문에 테이프를 시작 점에 붙히고 붙힌 곳 끝 점과 그 다음 지점을 확인합니다.

3. 반복문의 탈출 조건은 물이 새는 곳의 위치를 다 확인하였을 때 입니다.

 

 

더 자세한 설명은 주석을 통해 하겠습니다.

 

↓↓↓↓↓↓↓↓↓↓  ↓↓↓↓↓↓↓↓↓↓↓  ↓↓↓↓↓↓↓↓↓↓↓  ↓↓↓↓↓↓↓↓↓↓↓

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
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));
        // 입력
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        // 출력
        StringTokenizer stok = new StringTokenizer(br.readLine());
       
        int n = Integer.parseInt(stok.nextToken()); //구멍 개수
        int l = Integer.parseInt(stok.nextToken());	//테이프 길이
        int[] arr = new int[n];
        stok = new StringTokenizer(br.readLine());
        for(int i = 0;i<n;i++){
            arr[i] = Integer.parseInt(stok.nextToken());
        }
        Arrays.sort(arr); //구멍을 위치 순서대로 정렬

        int head = 0;	//확인 할 곳 시작점
        int tail = 1;	//확인 할 곳 끝점
        int cnt = 0;	//테이프 붙히는 개수
        while(true){
            if(tail==arr.length){	//끝지점이 배열의 크기과 같다면
            						//head와 tail사이에 구멍 한개가 있으므로 
                cnt++;	//테이프를 붙히고
                break;	// 반복문 탈출
            }
            if(arr[tail]-arr[head]<l){	//끝지점과 시작지점의 차이가 L보다 작으면
                if(arr[tail]-arr[head]+1==l) {	//+1한 값과 같다면
                    cnt++;			//테이프를 붙히고
                    head = tail+1;	//더 이상 붙힌 곳을 보지 않는다
                    tail = head+1;
                }
                else tail++;		//그렇지 않다면 끝지점만 늘려서 다음에
                					//사이값을 다시 비교한다
            }
            else{				//끝지점과 시작지점의 차이가 L보다 같거나 크면
                cnt++;			//테이프를 붙히고
                head=tail;		//겹쳐붙히기 위해
                tail=head+1;	//끝지점과 그 다음지점을 비교한다
            }
            if(head==arr.length){	//끝까지 봤다면 반복문을 탈출한다
                break;
            }
        }
        bw.write(String.valueOf(cnt)); //출력
        bw.flush();
    }
}