99클럽 코테 스터디 19일차 TIL + DP

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

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
inf = 1e7
dp = [inf] * (n+1)
dp[0] = 0

for i in range(n):
    if i <= n:
        dp[i+1] = min(dp[i+1], dp[i]+1)
    if i+i//2 <= n:
        dp[i+i//2] = min(dp[i+i//2], dp[i]+1)

if dp[n] <= k:
    print("minigimbob")
else:
    print("water")

 

• i+1번째 계단에 올 수 있는 횟수는 두가지 방법으로 구할 수 있다.
  • 이전 칸에서 한칸 오르기 > 기존횟수 + 1
  • i+i//2 칸 오르기 > 기존횟수 + 1
• 즉 기존 자신의 횟수와 이전 칸 (i) 에서 올라오는 횟수를 비교해 최솟값을 가지고 있으면 된다.
• n개의 계단을 돌면서 횟수를 구해주고 k횟수 보다 적다면 k횟수 안에 계단에 도달한 것이기 때문에 minigimbob 출력
• k횟수 보다 많다면 k횟수 안에 도달하지 못했기 때문에 water 출력