백준 1654번: 랜선 자르기 - Swift 풀이

오늘의 문제

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

 

이게... 최소한 내 머릿속에서라도 일정한 규칙대로 예제가 풀려야 코드로 구현을 하든가 말든가 하는데 그냥 내 머리로도 예제 입력 1을 어떻게 처리해야 200이 나오는지 모르겠어서 한참 걸렸다.

 

이분탐색인 거 알아도 뭘 어디에 이분탐색을 적용해야 할지 감이 안 잡혀서 레전드 나누기만 하다가 결국 검색 찬스를 써서 해결했다. 코드를 보면 이해는 되는데 생각하는 걸 코드로 구현해내는 능력이 너무 부족한 듯. 너무 오랜만에 하려니까 다 까먹어버린 게 제일 크다. 다시 열심히 하겠습니다... 꾸준히가 제일 중요한 것 같다.

 

설명은 주석으로 적어놨는데 특히 주의해야 할 부분이

1. if-else문에서 numOfLAN과 N값이 같을 때 처리

2. start의 값을 0이 아닌 1로 초기화

이렇게 2가지 정도가 있다.

 

1. numOfLAN(= 잘린 랜선 개수의 총합)의 값이 N보다 크거나 같을 때 start를 mid + 1 해줘야 한다. numOfLAN과 N이 같을 때 start 쪽의 값을 변화시켜줘야 while문이 false가 되고, numOfLAN을 N과 같게 해주는 end 값이 최종 출력될 수 있기 때문이다.

 

2. 처음에 제출할 때 별생각 없이 start 값을 0으로 초기화 했었는데 한 90% 됐을 때에 런타임 에러가 발생했다. 이게 mid가 0이 될 가능성을 제공하기 때문이다. (참고: https://www.acmicpc.net/board/view/124805) 어차피 랜선의 길이가 0일 리도 없기 때문에, start는 1로 초기화를 해주는 게 맞다.

 

내 풀이

import Foundation

// 입력
let input = readLine()!.split(separator: " ").map { Int($0)! }
let K = input[0]
let N = input[1]

var LANS: [Int] = []

for _ in 0..<K {
    LANS.append(Int(readLine()!)!)
}

var start = 1 // 랜선의 최소 길이
var end = LANS.max()! // 랜선의 최대 길이
var numOfLAN = 0 // 랜선의 총 개수

// 범위가 꼬이지 않을 때까지 반복
while start <= end {
    let mid = (start + end) / 2 // 랜선의 중간값
    numOfLAN = 0 // 랜선 개수 초기화
    for i in LANS { // 입력받은 랜선 값들 하나씩 뽑아서
        numOfLAN += i / mid // 중간값으로 나누었을 때 몫을 다 더한다 -> 이게 N 이상이 되면 됨
    }
    
    if numOfLAN < N { // 랜선의 총 개수가 N보다 작다
	// mid가 더 작아져야 됨 -> 나누는 값이 더 작아져야 몫이 커지기 때문에
        end = mid - 1
    } else { // 랜선의 총 개수가 N 이상이다 -> 좋다 최대 랜선 길이를 찾아 떠나자
	// mid가 더 커져야 됨
        start = mid + 1
    }
}

// 범위가 다 좁혀졌을 때의 최대값 end를 출력
print(end)