[Python] 백준 11561번 : 징검다리 <Silver 3>

⚠️ 내맘대로 작성한 코드이기 때문에 비합리적 진행과 근거없는 추론이 있을 수 있습니다!⚠️

 

https://www.acmicpc.net/problem/11561

11561번: 징검다리

Code

---

import sys
input = sys.stdin.readline

cycle = int(input())

while cycle:
    cycle -= 1
    number = int(input())
    min, mid, max = 0, 0, number
    while True:
        mid = (min + max) // 2
        if (mid*(mid + 1)) //2 < number:
            if ((mid+1)*(mid+2)) // 2 > number:
                break
            else:
                min = mid + 1
        elif (mid*(mid + 1)) //2 > number:
            max = mid - 1
        else:
            break
    print(mid)

---

Code 필수 요소

1. 이분탐색 알고리즘

2. 정답 도출 식

 

이것만 생각해내면 절반은 끝났다.

 

// 이분탐색 알고리즘

먼저, 왜 이분탐색을 활용했을까?첫번째 단서는 숫자의 범위다. 최댓값이 10^16이기 때문에 범위가 상당히 크다. 그렇기때문에 반복문으로 하나씩 확인하는 방법은 불가능하다 판단했다.두번재 단서는 숫자의 규칙성이다. 최대한 많은 칸을 이동해야하고, 이전에 움직인 칸보다 무조건 더 움직어야 하기 때문에 1 + 2 + 3 + 4 + ... 와 같은 식으로 진행될 것이다. 그렇다면 등차수열의  합을 구하는 공식을 이용해서 값을 도출하고, 이분탐색을 활용하고자 했다.

 

이분탐색 알고리즘이 뭔지에 대해서 간단히 설명하겠다. 범위를 잡고, 해당하는 값이 나올때까지 절반을 제외시키는 방법으로 값을 도출하는 방법이다. 그렇기 때문에 제일 작은 값인 min, 제일 큰 값인 max, 절반 나누기 위한 중간값 mid를 설정해둔다.

 

max를 number로 설정한 이유는 간단하다. 한번에 한칸씩 움직일 경우 number의 값이 나온다. 하지만 반드시 이동중 칸 수를 늘려가며 이동해야 하기 때문에 number보다 큰 수가 나올 수 없다.

 

// 정답 도출 식

등차수열의 합을 구하는 식을 이용해서 입력받은 값과 비교하여 정답을 도출 했다.mid의 값이 입력받은 값보다 작고, mid+1이 입력받은 값보다 클 경우 정답으로 도출했다.예를들어 칸이 9개가 있다면 마지막 한칸을 반드시 밟아야 하기 때문에 1 + 2+ 6으로 진행해야 한다. 그렇기 때문에 1 + 2 + 3의 값을 구하고, 1 + 2 + 3 + 4의 값을 구한다. 1 + 2 + 3의 값은 6이므로 9보다 작고, 1 + 2 + 3 + 4의 값은 9보다 크다. 이러한 분기점을 찾아내는 방식으로 정답을 구했다.또한 운 좋게 딱 떨어지는 숫자일 경우를 위해 일치할경우 반복문을 탈출하도록 설정해 두었다.

 

푸는것 자체는 쉽게 했는데 식이 좀 조잡한거 같다. 다른분들의 코드를 보니까 나보다 훨씬 깔끔하기도 하고 소요 시간도 짧은거 같던데... 아쉽.

 

 

-꿑-