Today's keyword : 이진탐색
문제설명
주어진 징검다리의 개수에 따라 건너야 하는 수를 최적화하는 문제로, 주어진 징검다리의 개수 n이 있을 때, 1부터 n까지의 수 중에서 가장 많이 건널 수 있는 수를 찾는 것이 목표
https://www.acmicpc.net/problem/11561
문제풀이
이 문제에서 포인트는 두 번째 점프부터는 이전의 점프한 거리보다 1 이상 긴 거리를 뛰어야 한다는 것이다. 최대 징검다리 수를 출력한다고 하면 가장 이상적인 점프 방식은 처음에 한 칸 뛰고, 그 다음 두 칸 뛰고, 그 다음 세 칸 뛰는 식으로 점프하는 거리를 한 칸씩 늘리는 것이다. 징검다리를 건너기 위한 최소한의 수는 한 칸씩 점프 이동거리를 늘린 거리의 합이기 때문에 수식으로 작성하면 N*(N+1)/2가 되기 때문에 해당 조건과 주어진 징검다리 수와 비교한다.
마지막에 점프를 더 멀리하던지, 초반에 시작지점을 늘리는 방식으로 충분히 수정 가능하기 때문에 승택이가 움직이는 최소한의 이동거리가 징검다리보다 작거나 같아야 하며, 승택이의 이동거리가 징검다리 수보다 크면 좀 더 적은 수를 탐색하도록 중간 인덱스를 작게 조정하고, 이동거리 수가 작거나 같으면 승택이가 건너는 수가 최대가 되도록 중간 인덱스를 크게 조정한다.
# 백준 징검다리 : 11561
t = int(input())
for _ in range(t):
n = int(input())
start = 1
end = n
result = 0
while start <= end:
mid = (start + end) // 2
if ((mid + 1) * mid) // 2 <= n: # 건너야 하는 수가 징검다리 개수보다 작으면 -> 오른쪽 탐색
start = mid + 1
result = mid
else: # 징검다리 개수보다 큰 경우 -> 왼쪽 탐색
end = mid - 1
print(result)사용 변수
- t: 테스트 케이스의 수
- n: 징검다리의 개수
- start: 탐색의 시작점 (1)
- end: 탐색의 끝점 (n)
- result: 최적의 수를 저장할 변수
코드 설명
- while start <= end: 시작점이 끝점보다 작거나 같을 때까지 반복합니다.
- mid = (start + end) // 2: 중간값을 계산합니다.
- if ((mid + 1) * mid) // 2 <= n: 중간값을 사용하여 건널 수 있는 수가 징검다리의 개수보다 작거나 같은지 확인합니다.
- 조건을 만족하면, start를 mid + 1로 이동시키고, result에 mid를 저장합니다.
- 조건을 만족하지 않으면, end를 mid - 1로 이동시킵니다.
오늘의 회고
이진탐색을 할 때는 조건 설정이 중요하다!