(JAVA) 백준 1449번 : 수리공 항승

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

1449번: 수리공 항승

 

그리디 알고리즘 문제.

 

난이도는 하! (내가 한번에 풀어서)

 

 

 

 

 

매커니즘

---

구멍의 좌우로 0.5 센치씩은 확보해야 한다고 했으므로

하나의 구멍을 메꾸기 위해서는 테이프 길이 1을 사용해야 한다.

 

 

예제를 통해 풀이 방법을 알아보면

 

input:

4 2

1 2 100 101

 

 

-> 테이프의 길이 : 2cm

-> 2 - 1 : 1cm

좌우로 0.5cm 확보하면 구멍 1, 2를 메꾸기 위해 0.5cm ~ 2.5cm 지점에 테이프를 붙이면 된다.

즉, 2cm 테이프의 길이로 구멍 1, 2를 메꿀 수 있다.

 

 

 

0) pipe int배열 생성

 

1) 저 구멍을 담은 배열을 오름차순 정렬한다.

 

2) 첫 번째 구멍부터 끝까지 탐색 시작(for문)

 

3) 선택한 구멍과 다음 구멍의 차이와 테이프 길이를 비교

 

3-1) 다음 구멍 - 선택한 구멍 > 테이프의 길이 - 1 인 경우 다음 구멍 탐색(count 1 증가시키지 않음)

*** 좌우로 0.5센치를 더 붙여야 하기 때문에 테이프의 길이에서 1cm를 뺀 길이만큼 구멍 간격이 있어야 그 구멍을 메꿀 수 있다.

 

3-2) 3-1을 만족하지 않은 경우에 count를 1 증가시키고 다음 구멍 탐색

 

4) count 출력

 

 

 

 

감사합니다.

 

소스코드

---