[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()

 

 

🔥 강평

---

 

이분 탐색을 떠올리기가 아직 어렵다. 처음에 문제를 접할때 어떻게 쪼개서 살펴봐야할지를 잘 생각해봐야한다고 생각이 든다

그와 별도로 백준 서버에서 실행되는 코드와 내 로컬에서 실행되는 코드를 구분해서 작성해봤다. 매번 검증할 때마다 노가다로 타이핑하고, 백준에 올릴때는 또 코드를 수정해야했던게 매우매우 귀찮았는데, 이제 그런 귀찮은 일 아예 없겠다. 우하하