[백준/DP] 2266번 금고 테스트

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

2266번: 금고 테스트

 

 

N층에 K개의 금고를 가진 상황에서, i 층에서 금고를 떨어뜨렸다면

깨졌을 경우 => i-1층에 k-1개의 금고를 가진 상황에 + 1 횟수

안 깨졌을 경우 => N-i 층에 K 개의 금고를 가진 상황에 + 1 횟수

 

D[k][n] = n층에서 k개의 금고를 가지고, F층을 알아낼 수 있는 최소의 금고 낙하 횟수

 

최악의 경우중에서 최소를 구하면 된다.

 

import sys

input = sys.stdin.readline

n,m = map(int,input().split())

#최대가 500층임
dp = [[0] * 501 for _ in range(501)]

#1층, 0층에서 떨어지는 횟수 초기화
for i in range(1,m+1):
    dp[i][1]=1
    dp[i][0]=0
#i층에서 금고 1개로 확인할 수 있는 최소 횟수는 i번
for i in range(1,n+1):
    dp[1][i] = i
#2개 가지고 있는 개수만큼
for i in range(2,m+1):
	#2층 부터 층만큼
    for j in range(2,n+1):
    	#min을 구하는 것이므로, 최댓값으로 초기화
        dp[i][j] = 1000000000
        # i개의 금고를 가질 때, 각 층에서 최솟값구하기
        for k in range(1,j+1):
            dp[i][j] = min(dp[i][j],1+max(dp[i-1][k-1],dp[i][j-k]))
print(dp[m][n])

Python으로는 시간 초과가 떠서, pypy로 했다.