[Python][BoJ] 29717 슬라임 잡고 레벨 업!

 

 

목차

 

 

🫡 Overview

체감 난이도: ★★☆☆☆

소요시간: 

문제 레벨: 실버2 / 문제 유형: 수학, 이분탐색
풀이 상태:  답안참고
추후: 다시 풀어보기

 

 

---

문제 링크

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

요구사항 분석

목표: 슬라임 N마리를 처치할 경우 몇 레벨로 성장할 수 있는지 계산하기

- 경험치 획득: 지금까지 처치한 몬스터 수(x) +1
- 각 레벨업에 필요한 경험치 y =  2*(level)
  - 레벨업 시 경험치 소진 y만큼 소진
- 초기 유저 세팅: 레벨 1, 경험치 0
------------------------------

 

나의 코드

• 현재 몬스터를 k 마리 처리했다고 했을 때, 누적 경험치 : f(k) = k(k+1)/2 
  • 등차수열 1,2,3,..,K의 누적합 : k(k+1)/2
• 레벨 l 로 성장하기 위해 필요한 경험치의 합: l(l+1), (l = 1,..) 
  • 등차 수열 2,4,6,8,10,.. 의 누적합 -> l(l+1)
• 문제: 몇 레벨까지 성장할 수 있는가? 
  • 나의 누적 경험치 k(k+1)/2 가 성장 누적 경험치  l(l+1) 보다 커지는 최대의 l을 찾으면 된다. 
• 알고리즘 선택
  • N이 너무 크니까 (10**9) O(logN)의 시간복잡도를 가지는 이분 탐색을 선택했다.

 

def find_level(N:int) -> int:
    """
    몬스터 킬수가 들어오면 몇 레벨 상승했는지 이분 탐색으로 반환해주는 함수
    - 경험치의 합:  n(n+1)
    :param N:
    :return:
    level: 상승 레벨 수
    """
    cur_exp = N * (N + 1) // 2 # 현재 나의 경험치 누적값, N은 죽인 몬스터의 수 
    l, r = 1, 10**9
    level = 0
    while l <= r:
        m = (l + r) // 2
        need = m*(m + 1)
        if cur_exp >= need: # 경험치가 충분하면 더 높은 레벨로 업뎃 가능
            level = m
            l = m + 1
        else:
            r = m - 1
    return level

T = int(input()) # 테스트 케이스의 수 1<=T<=1000
for _ in range(T):
    N = int(input()) # 1 <= N <= 10**9
    level_d = find_level(N)
    print(level_d+1)

 

Obstacles 

이분 탐색 시, 정답값 업데이트 조건을 제대로 설정해줄 필요가 있다. 

- 정답값을 언제 업데이트 해줄 것인가? 

   : 문제에서 나의 누적 경험치가 레벨업 필요 경험치 보다 (1) 크거나 (2) 같을 때, 더 높은 레벨로 업데이트 가능한다. 

   -> 레벨을 업데이트하고, 더 큰 레벨 범위에서 탐색을 시작한다. 

---

배운 점/느낀 점

이분 탐색 알고리즘에 대해서 더 잘 알게 되었습니다.