ℹ️ 문제 정보
| 플랫폼 | 번호 | 제목 | 유형 | 난이도 | 언어 |
|---|---|---|---|---|---|
| 백준 | 11561 | 징검다리 | 이분탐색 | 실버3 | Swift |
🚀 나의 접근 방법
입력 조건을 보면 1 ≤ N ≤ 10^16으로 매우 크기 때문에 이분탐색으로 접근했다.
- 첫 징검다리는 점프해서 아무 것이나 밟을 수 있다. 이 점프가 첫 점프이다.
- 두 번째 점프부터는 이전에 점프한 거리보다 1 이상 더 긴 거리를 뛰어야만 한다.
- N번 징검다리는 반드시 밟아야 한다.
- N번 징검다리를 밟은 후 강 건너로 이동할 땐 점프를 하지 않으므로 위의 규칙이 적용되지 않는다.
위 문제 조건을 유의해서 풀이 방법을 떠올려야 한다.
조건에 따라 밟는 징검다리의 수를 최대로 하려면 1칸 이동, 2칸 이동, 3칸 이동 ...처럼 다음번에 뛸 때 +1칸 만 더 뛰면 된다. 최대한 많이 밟아야 하니 굳이 +2칸 할 필요는 없다.
그래서 징검다리의 개수가 10개일 때, 승택이가 밟을 수 있는 징검다리의 최대 수는 4개이다.
승택이가 밟은 징검다리의 수를 K이라 했을 때 1 ~ K의 합(1+2+3+4=10)은 10(징검다리의 개수)이다.
하지만 여기서 의문이 들 수 있다. 징검다리의 개수가 9개 일 때는 어떨까??
위처럼 +1칸씩만 늘리면 마지막에 4칸 이상을 뛰어야 하는데 그렇게 되면 조건 4를 위반하게 된다.
이때 어렵게 생각할 필요 없이 위처럼 마지막 3칸을 6칸 뛰는 것으로 대체하면 된다.
정리하자면, 승택이가 밟은 징검다리의 수를 K이라 했을 때 1 ~ K의 합이 징검다리의 개수 보다 작거나 같은 값 중 최댓값을 찾으면 된다. (1 ~ K의 합은 등차수열의 합 공식 활용, (K+1)*K/2)
다음으로 이분 탐색 범위를 정해야 하는데 입력 조건 N의 최댓값이 10^16(1경)으로 매우 크다. 이 범위를 등차수열의 합 공식 (K+1)*K/2을 돌리면 Int64 범위를 초과할 수 있다. 때문에 단순 계산으로 10^8(10억)까지 범위를 정하면 무사히 계산할 수 있다.
✍️ 나의 코드
let T = Int(readLine()!)!
for _ in 0..<T {
let N = Int(readLine()!)!
var start = 0
var end = 1000000000
while start <= end {
let mid = (start + end) / 2
let sum = (mid + 1) * mid / 2
if N < sum {
end = mid - 1
} else {
start = mid + 1
}
}
print(end)
}🤔 회고 및 개선사항
1 ~ K의 합 계산하기(등차수열의 합 공식)
수학 문제가 아니어도 코딩 테스트에서는 알고 있으면 좋은 수학 공식들이 있다. 특히 등차수열의 공식이 자주 나오는 편이다. 이번 기회에 등차수열의 합 공식을 제대로 기억하자. (K+1)*K/2
탐색 데이터 범위 결정
처음에는 10^16까지 범위를 설정하여 문제를 해결할 수 없었다. 항상 큰 범위가 주어지면 자료형의 범위를 고려하여 문제를 해결할 필요가 있다.
