목록백준 (1)
PS 부수기
백준 1126 같은 탑
dp[index][heightDif] = index번째 블록부터 사용했을 때(사용을 고려했을 때), 그리고 현재 두 탑의 높이차이가 heightDif일 때 미래에 세워질 두 탑의 높이 중 높은 높이의 최댓값이다. 우리가 구하려하는 답은 dp[0][0]임을 알 수 있다. Case 1 : index번째 블록을 사용하지 않는다. -> 변한건 없이 바로 dfs(index+1, heightDif)를 호출 Case 2 : index번째 블록을 더 높은 탑에 쌓는다. -> heightDif는 a[index]만큼 더 늘어날 것이다. 그리고 탑의 최대 높이도 a[index]만큼 늘어날 것이다. Case 3 : index번째 블록을 더 낮은 탑에 쌓는다. -> heightDif는 a[index]-heightDif의 절댓값..
PS
2020. 8. 5. 21:30