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

Overview

• 체감 난이도: ★★☆☆☆
• 문제 레벨: 실버 2
• 문제 유형: 이분탐색
• 풀이 상태: 답안참고 / 스스로 해결
• 추후: 다시 풀어보기 / 간단 복습 / 완벽 이해 

---

[문제]

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

 

# 처치한 슬라임 수 : x
# 새로운 슬라임을 처치하면 x + 1 만큼의 경험치

# 현재 레벨에서 레벨업에 필요한 경험치: y
# 레벨업 후 경험치 y를 소모한 뒤 다음 레벨업에 필요한 경험치는 y + 2
# 레벨 1의 경우 레벨업에 필요한 경험치는 2이다.

# 신규 유저는 레벨 1, 경험치 0으로 시작 / 슬라임 수 0

# Q. N마리를 처치할 경우 레벨이 몇이 될 지 출력

 

[코드]

✔︎ dp + 반복문으로 푼 코드(시간 초과)

- n을 입력 받을 때마다 dp 배열 새로 생성 → 시간초과 

def need_exp(n):
    dp = [0] * (n+1)
    dp[1] = 2

    for i in range(2, n+1):
        dp[i] = dp[i-1] + 2

    return dp


def slime_exp(n):
    dp = [0] * (n+1)

    for i in range(1, n+1):
        dp[i] = dp[i-1] + 1

    return dp


T = int(input())
for t in range(T):
    n = int(input())

    lst = need_exp(n)  # 레벨업에 필요한 경험치 리스트
    exp = sum(slime_exp(n))  # 슬라임 처치 경험치

    lv = 1
    for i in range(1, n+1):
        if exp - lst[i] < 0:
            print(lv)
            break
        else:
            lv += 1
            exp -= lst[i]

 

✔︎ dp + 이분 탐색 코드(런타임 에러)

- Input값이 10**9까지인데 dp 메모리를 10**9 로 설정해주니 값이 너무 커 KeyboardInterrupt가 발생했다. 

mn = 10**5
dp = [0, 2, 6] + [0] * (mn-2)
y = 6

for i in range(3, mn):
    dp[i] = dp[i-1] + y
    y += 2


T = int(input())
for t in range(T):
    n = int(input())
    exp = n * (n+1) // 2

    lv, left, right = 1, 0, n

    while left <= right:
        mid = (left + right) // 2

        if dp[mid] <= exp:  # 경험치가 충분하면 더 높은 레벨 가능
            lv = mid
            left = mid + 1
        else:  # 경험치가 부족하면 더 낮은 레벨을 찾는다.
            right = mid - 1

    print(lv+1)

 

✔︎ 최종 코드(이분탐색)

- dp 배열을 없애고, mid 값을 이용해 비교해줄 때마다 계산해주었다. 

- 필요한 exp는 2, 4, 6, 8, 10, ..., n → 2씩 증가 ► 2 * ( n * (n + 1) // 2) = n * (n + 1)

- 슬라임 처치 시 획득하는 exp는 1, 2, 3, 4, 5, 6, ..., n → 1씩 증가 ► n * (n + 1) // 2

T = int(input())
for t in range(T):
    n = int(input())
    exp = n * (n+1) // 2

    lv, left, right = 1, 0, n

    while left <= right:
        mid = (left + right) // 2
        need = mid * (mid + 1)

        if need <= exp:  # 경험치가 충분하면 더 높은 레벨 가능
            lv = mid
            left = mid + 1
        else:  # 경험치가 부족하면 더 낮은 레벨을 찾는다.
            right = mid - 1

    print(lv+1)