728x90
반응형
https://www.acmicpc.net/problem/28069
28069번: 김밥천국의 계단
첫 번째 줄에 계단 개수에 해당하는 $N$, 계단을 오르는 횟수 $K$가 주어진다. $(1 \leq N, K \leq 1\,000\,000)$
www.acmicpc.net
문제
민희는 미니김밥이 유명한 천국에 가려고 합니다.
천국 문 앞에는 무한히 많은 계단이 있고 가장 아래 계단의 번호가 0번이며, 위로 올라가면서 순서대로 번호가 붙어있습니다. 그중 번째 계단 옆에 김밥 가게가 있습니다.
민희는 매번 다음의 2가지 행동 중 하나를 선택해서 총 번 행동할 수 있으며, 정확히 번째 행동에서 번째 계단에 도달하면 미니김밥을 먹을 수 있습니다.
- 계단 한 칸을 올라갑니다.
- 민희가 집에서 가지고 온 지팡이를 계단에 두드립니다. 만약 민희가 번째 계단에서 지팡이를 두드리면 번째 계단으로 순간이동합니다.
현재 민희는 0번째 계단에 있습니다. 민희가 미니김밥을 먹을 수 있을지 구해 봅시다.
입력
첫 번째 줄에 계단 개수에 해당하는 , 계단을 오르는 횟수 가 주어진다.
출력
민희가 개의 계단을 번 만에 올라 미니김밥을 먹을 수 있으면 minigimbob을, 그러지 못해 물만 마신다면 water을 출력한다.
풀이
Code
import sys
input = sys.stdin.readline
n, k = map(int, input().split())
# 1. dp 생성
dp = [float("INF") for _ in range(n+1)]
# 2. 초기값 설정
dp[0] = 0
# 3.
for i in range(1, n+1) :
# 3-1. 이전 계단에서 올라오는 경우
dp[i] = min(dp[i], dp[i-1] + 1)
# 3-2. 순간이동이 가능한 경우
if i + i // 2 <= n :
dp[i + i // 2] = min(dp[i + i // 2], dp[i] + 1)
# 4. 결과 출력
print("minigimbob" if dp[-1] <= k else "water")
728x90
반응형
'Coding Test > Baekjoon' 카테고리의 다른 글
[Python/BOJ] 1238. 파티 (1) | 2024.01.25 |
---|---|
[Python/BOJ] 2698. 인접한 비트의 개수 (0) | 2024.01.23 |
[Python/BOJ] 13023. ABCDE (1) | 2024.01.22 |
[Python/BOJ] 12763. 지각하면 안 돼 (1) | 2024.01.19 |
[Python/BOJ] 11401. 이항 계수 3 (0) | 2024.01.09 |