[99클럽 코테 스터디 1일차][백준 11561]징검다리 (파이썬 풀이)
🤔 문제 설명 및 입출력
✍ 접근 방법
최대한 많은 스탭을 밟으려면 무조건 전에 뛰었던 스탭보다 딱 1만큼 많이 가야한다는 아이디어에는 도달했다.
그래서 음 N-1, N-2 .... 1 까지 모두 더하고, 이 값이 N과 같으면 정답으로 하고, N보다 크면 시작점을 1 줄여서 진행해야지~ 라고 생각했는데... 사고를 전개하다보니 뭔가 비효율적이라는 느낌이 들었다. 그리고 이런 일일히 노가다식 덧셈이 딱 N과 맞을꺼라는 보장이 들지 않았다.
좀 더 생각해보니까, 결국 전 스탭보다 1 스탭만큼 더 가는 행마를 어떻게든 우겨넣으면 최대 징검다리 밟은 개수가 된다는 사실을 찾아냈고, 이를 노가다로 다시 찾으려다가? 이분 탐색을 이용해서 찾기로 했다 (NOTE: 정렬된 리스트 내에서 특정 값을 search할때는 이분 탐색부터 생각해봐라 )
1부터 시작해서 N에 도착하는데, 전 스탭보다 딱 1만큼 더 가는 것은 등차수열의 합으로 구할 수 있으니, 이분탐색의 매 mid를 등차수열의 합으로 두고, 이 값이 돌의 전체 개수보다 큰 지 작은 지를 비교해서 탐색 범위를 줄이면 된다.
만약 탐색범위 초과 (left > right) 인 경우, right를 초과해서 넘어가면 정답 조건을 만족할 수 없으니, 최대로 갈수 있는 돌은 right까지인걸로 간 주하고, right에서 N번째 돌까지 한번 폴짝 뛰는 것으로 처리한다.
👨💻 소스 코드
- 파이썬
# 11561
# 문제 링크 : https://www.acmicpc.net/problem/11561
import os
import json
def is_local_environment(config_file='local-config.json'):
if os.path.exists(config_file):
with open(config_file, 'r') as file:
config = json.load(file)
return config.get('local') == bool('true')
return False
def read_local_file(file_name:str)->None:
f = open(file_name)
if f == False:
return None
T = f.readlines()
f.close()
T = [int(line.strip()) for line in T]
return T
# 조건
# N번 징검다리는 반드시 밟아야 한다.
# 첫번째 징검다리는 아무것이나 밟을수 있다
# 두번째 점프부터는 이전에 밟은 징검다리의 번호보다 커야한다
# 1 <= number_of_stone <= 10**16
# 밟을 수 있는 최대 징검다리의 수는?
# 최대로 많은 징검다리를 밟으려면 1,2,3,...N-1,N 순으로 계속 1씩 커지면서 밟기
# 1씩 커지는 순서쌍을 어떻게든 우겨넣어야한다. (시작 다리만 바꾸는 방식으)
# 이분 탐색으로 찾기..
def binary_search(left: int, right: int, total_stone: int) -> int:
if left > right:
return right
mid = (left + right) // 2
sum_of_stone = mid * (mid + 1) // 2
if sum_of_stone == total_stone:
return mid
elif sum_of_stone > total_stone:
return binary_search(left, mid - 1, total_stone)
else:
return binary_search(mid + 1, right, total_stone)
def solution(number_of_stone:int)->int:
result = binary_search(1, number_of_stone, number_of_stone)
return result
def main():
# local환경 실행
if is_local_environment():
local_data = read_local_file('11561.txt')
number_of_stone = local_data[0]
for i in range(1,number_of_stone+1):
print(solution(local_data[i]))
# BOE환경 실행
else:
number_of_stone = int(input())
for i in range(number_of_stone):
print(solution(int(input())))
main()
🔥 강평
이분 탐색을 떠올리기가 아직 어렵다. 처음에 문제를 접할때 어떻게 쪼개서 살펴봐야할지를 잘 생각해봐야한다고 생각이 든다
그와 별도로 백준 서버에서 실행되는 코드와 내 로컬에서 실행되는 코드를 구분해서 작성해봤다. 매번 검증할 때마다 노가다로 타이핑하고, 백준에 올릴때는 또 코드를 수정해야했던게 매우매우 귀찮았는데, 이제 그런 귀찮은 일 아예 없겠다. 우하하
