99클럽 코테스터디 19일차 TIL - 백준 28069

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

해당 문제는 DP로 풀이했다.

- 0번 계단부터 N번째 계단까지 도달하는 종료 조건이 있음

- DP[N]을 N번째 계단까지 도달하기 위해 행동한 횟수라고 가정하여 점화식을 세울 수 있음

 

❌ 틀린 풀이

n, k = map(int, input().split())
INF = int(1e9)
dp = [INF] * (n+1)   # DP[i]: i번째 계단까지 도달하기 위한 행동 횟수
dp[0] = 0    # 현재 0번째 계단에 있고, 행동횟수는 0이므로 dp[0] = 0으로 초기화

for i in range(n):
  if i + 1 <= n:
    dp[i+1] = min(dp[i+1], dp[i] + 1)
  if i + i/2 <= n:
    dp[int(i + i/2)] = min(dp[int(i + i/2)], dp[i] + 1)
    # [x]는 x보다 작거나 같은 가장 큰 정수 --> 소수점을 제거한 정수와 같다.
    # int(i+i/2) : [x]는 x보다 작거나 같은 가장 큰 정수 --> 소수점을 제거한 정수와 같다.

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

 

그러나! 이부분은 틀린 풀이이다.

다른 분들의 풀이를 찾아보니 마지막 조건이 dp[n] == k 가 아니라 dp[n] <= k 임을 확인할 수 있었다.

 

왜 조건이 dp[n] <= k 인지 이해해보자면

- 문제 조건에서 "2가지 행동 중 하나를 선택하여 총 K번 행동"  --> 즉 k 번 이내에 도달할 수 있으면 됨

- 만약 0번째 계단에서 지팡이를 통해 계단을 두드릴 경우, i + i//2가 0이므로 dp[0] 에서 증가하는 계단이 없는데도 횟수를 소모하게 됨

즉, 꼭 K번의 행동횟수를 하지 않아도 K번 이내에 2가지 행동 중 하나를 시행할 시 계단에 도달할 수 있다면 해당 값이 정답이 됨

 

따라서 마지막 조건을 dp[n] <= k 로 수정하여, 반드시 k번의 행동을 하지 않아도 그 이내에 n번째 계단에 도달할 수 있는지 판단할 수 있도록 수정해야한다.

 

✅ 정답 풀이

n, k = map(int, input().split())
INF = int(1e9)
dp = [INF] * (n+1)   # DP[i]: i번째 계단까지 도달하기 위한 행동 횟수
dp[0] = 0    # 현재 0번째 계단에 있고, 행동횟수는 0이므로 dp[0] = 0으로 초기화

for i in range(n):
  if i + 1 <= n:
    dp[i+1] = min(dp[i+1], dp[i] + 1)  # 기존 계단 한칸 더 올라간 행동횟수와 현재에서 행동횟수를 한번 더 했을때를 비교
  if i + i/2 <= n:
    dp[int(i + i/2)] = min(dp[int(i + i/2)], dp[i] + 1)
    # int(i+i/2) : [x]는 x보다 작거나 같은 가장 큰 정수 --> 소수점을 제거한 정수와 같다.

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