백준 11561 문제 풀이
문제
승택이는 강을 건너려 한다.
승택이는 수영을 못하기 때문에, 강에 놓인 징검다리를 밟고 건너갈 것이다.
승택이는 수영은 못하지만 제자리뛰기는 정말 잘한다. 원하는 어느 곳으로든지 점프해서 바로 갈 수가 있다.
승택이는 이제 강의 한쪽 변 앞에 서 있다.
강엔 1번부터 시작해 2번, 3번, ... , N번 징검다리가 차례대로 놓여 있다.
강의 폭이 넓은 탓에 징검다리의 수는 엄청나게 많다.
이 징검다리를 모두 밟고 싶지는 않았던 승택이는 제자리뛰기 실력을 발휘해 적절한 개수의 징검다리만을 밟고 가기로 했다.
물론 강 건너편으로 바로 점프하는 것도 가능하지만, 더 재미있게 강을 건너기 위해 승택이는 다음과 같은 규칙을 정했다.
[조건사항]
첫 징검다리는 점프해서 아무 것이나 밟을 수 있다. 이 점프가 첫 점프이다.
두 번째 점프부터는 이전에 점프한 거리보다 1 이상 더 긴 거리를 뛰어야만 한다.
N번 징검다리는 반드시 밟아야 한다.
N번 징검다리를 밟은 후 강 건너로 이동할 땐 점프를 하지 않으므로 위의 규칙이 적용되지 않는다.
승택이가 위의 규칙을 지키며 강을 건널 때, 밟을 수 있는 징검다리의 최대 수는 몇 개일까?가 주어졌을 때, 형택이가 게임을 최소 몇 번 더 해야 Z가 변하는지 구하는 프로그램을 작성하시오.
문제 해석하기
- 테스트 케이스 T 입력받기
- 총 T개의 징검다리 수를 입력받기 ⇒ for문을 이용해서 값 받기
- 밟을 수 있는 징검다리의 최대수라고한다면?
- 첫번째 밟을때 멀리가지 않고 바로 1번을 밟는 경우
- 1번을 밟고 나면 1이상이니까 1+1의 점프를 하기
- 등차수열을 이용해서 1,2,3,4,5이런 식으로 1이상 긴 거리를 뛰기
- 이분 탐색, 이진 탐색을 이용해서 값 찾아내기
- 등차수열의 합 공식 이용하기
- (n*(n+1)) // 2
그래도 1일차에서 공부했던 이분탐색 덕분에 문제에 접근하는 것이 쉽게 느껴졌다
mid를 가지고 등차수열 식을 이용해서 코드를 작성해주면 되는 코드였다
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)등차수열
등차수열이란?
일정한 차이로 증가하거나 감소하는 수열이다. 가장 일반적인 형태로, 처음 항이 1이고 공차가 1인 수열을 고려할 수 있다
코드 내 등차수열 사용 방식
(mid + 1) * mid // 2 <= n- 이 구문은 등차수열의 합이 n보다 작거나 같은지 확인하기 위해 사용된다
- mid 값이 n의 값에 맞춰 조정되며, (mid + 1) * mid // 2이 실제로 n보다 작거나 같을 때까지 start와 end 값을 변경하여 이진 탐색을 수행한다
오늘의 회고
항해 99에서 비록 이제 2일차지만, 내가 문제를 풀수 있다는 사실이 좀 놀라운 것 같다. 차근차근 문제를 해석하고 풀어나가는 과정에서 조금씩 흥미를 느끼고 있는 것 같다.
등차수열을 너무 오랜만에 봐서 살짝 멈칫하긴 했지만, 이렇게 하나하나 공부하다보면 더 발전할 수 있다는 생각에 기대가 된다.
