[백준] 1449번 수리공 항승

생각

Github - https://github.com/hellojdh/Code/blob/master/src/baekjoon/q1000/Q1449.kt

길이가 L인 테이프를 최소로 사용하여 파이프 수리를 하고자 한다. 최소로 사용한 개수를 출력하여라.

처음 생각

파이프의 양쪽을 0.5 만큼 덮어야한다. 파이프의 고장난 곳은 무조건 정수이므로 0.5는 수리를 하는데 아무런 영향을 끼치지 못한다.

▶ 따라서 양쪽의 0.5를 못쓴다 생각하고 처음 입력받은 테이프의 길이 L에서 -1을 뺀 값을 테이프로 사용하였다.

다음 생각

고장난 부분만 살펴봐도 상관이 없지만 길이가 최대 1000밖에 안하므로 길이가 1000인 배열을 만들어 고장난 곳을 1로 표시하였다.

다다음 생각

배열을 처음부터 살펴보면서 값이 1인 즉, 고장난 곳을 발견하면 그 고장난 곳부터 L-1 만큼 0(고장나지 않음)으로 바꿔주었다.

방안

1) 앞에서부터 수리를 해나간것이므로 그리디 적인 접근인것 같다.

package baekjoon.q1000
 
import java.util.*
 
fun main(args:Array<String>){
    var sc : Scanner = Scanner(System.`in`)
    var n = sc.nextInt()
    // 양쪽의 0.5개의 사용을 미리 빼주기
    var L = sc.nextInt()-1
    // 최대 1000개
    var arr : Array<Int> = Array(1001,{0})
    for(i in 1..n)
        arr[sc.nextInt()] = 1
 
    var result = 0
    for(i in 1..1000){
        if(arr[i]==1){ // 물이 센곳이면
            result++ // 테이프 하나를 사용
            // L-1 길이만큼 사용해서 덮을 수 있는곳을 다 덮어주기
            for(j in i..(i+L)) {
                if(j==1001) break
                arr[j] = 0
            }
        }
    }
    println(result)
}