[BOJ/백준] 2695 공

DP 문제 테이블 방식은 2종류

 

dp[a][b] = a번의 횟수와 b의 높이가 남았을때의 최저 시도횟수

dp[a][b] = min(dp[a][b], 1 + max(dp[a-1][t-1], dp[a][b-t]))

1~b 사이에서 떨어드렸을 때, 깨지는 경우와 안깨지는 경우의 최악의 경우 max값을 구하고, 거기에 +1을 해준다.

횟수가 1회 남았을시에는 무조건 높이만큼의 횟수가 필요하니 그에 맞게 초기화

 횟수와 상관없이 1층만 남았을때에는 1회로 끝낼수 있으니 그걸로 초기화

 

 

 

다른 dp식 cozyyg 님의 코드를 보고 복기한거 틀릴 수 도 있음

 

dp[x][y] = x번 던질 기회가 남았을때 y번 시도해서 알 수 있는 유리가 깨지는 최소 높이

dp[x][y] = dp[x][y-1] + dp[x-1][y-1] + 1

y-1번을 시도했을때 x번 던질기회가 남았을때의 값과 ( 즉 깨지지 않았을때와) y-1번을 시도해서 x-1번 던질 기회가 남았을때(깨졌을때를 하면) 이 때의 최소높이는  이 두값을 더하고 + 1을 해준다.

 

두번째는 제대로 해석했는지는 모르겠다.