[백준] 1449번 수리공 항승 (그리디 알고리즘_JAVA)

스프링 공부하기 싫어서

풀어본 문제!

 

어려운 문제는 아니었다.

공부 편식하지말자아,,,

 

---

문제

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

1449번: 수리공 항승

 

 

---

설계

 

알고리즘 설계[접근방법] : 그리디 알고리즘

n 입력값이 1000이므로 배열을 사용했다!크기가 1000인 배열을 만들고, 입력받은 주소에 1를 저장했다. > 1은 수리가 필요한 공간이다.반복문을 돌며 1이면 테이프를 쓰고, 테이프를 다 쓰면 새로운 테이프를 쓰는 형식으로 풀었다.

 

여기서 중요한 점은, 배열의 값이 0이더라도 그 전에 테이프를 썼다면 테이프 값을 줄여야 한다는 것이다!

 

 

---

코드

import java.util.Scanner;

public class Test_1449_수리공항승 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		//배열 생성
		int[] arr = new int[1002]; 
		
		//물이 새는 곳 개수
		int n = sc.nextInt();
	
		//테이프 길이
		int length = sc.nextInt();
		
		//물 새는 곳 입력받기
		for(int i=0; i<n; i++) {
			arr[sc.nextInt()]=1;
		}
		
		//수리하기
		int tape = 0;
		int result = 0;
		for(int i=0; i<arr.length; i++) {
			//수리가 필요한 곳
			if(arr[i]==1 && 0<tape) { tape--; arr[i]=2;}
			else if(arr[i]==1 && tape<=0) { result++; tape=length-1;}  
			
			//수리가 필요 없는 곳
			else if(arr[i]==0 && tape!=length) tape--;
		}
		
		//출력
		System.out.println(result);
	
	}
}

 

 

(❁´◡`❁)

끝!