안녕하세요,
재재입니다.
BOJ 23963 계단 만들기 Small 문제 풀이입니다.
BOJ 23963 계단 만들기 Small
(1) 문제 설명
분류 : dynamic programming
출처 : https://www.acmicpc.net/problem/25963
(100 이하) N 개의 계단이 주어집니다.
계단을 최소한으로 옮겨서 인접한 계단 사이의 차이가 1이하가 되도록 만들면 됩니다.
이때, 계단은 한 번에 한 개씩 옮길 수 있습니다.
(2) 풀이 도출
만들 수 있는 계단의 최대 높이를 한번 고려해보면,
좋은 힌트가 될 수 있습니다.
이때, 최대 높이는 N을 넘을 수 없음을 보장 할 수 있습니다.
이 성질을 활용해서 문제를 해결한다면,
dynamic programming 으로 해결 할 수 있습니다.
dp[i][h][used] : i번째 계단을 h의 높이로 채운다고 하고,
바로 전까지 used 만큼 갯수를 사용했을 때 최적값
최초 계단의 h를 미리 정해두면,
그 다음의 상태는 h, h+1, h-1 로 변합니다.
이제 이 풀이를 발전시켜보면,
여기서 used 의 최대 합은 $$ n(n+1)/2 $$ 입니다.
이때, 전체 공간복잡도를 먼저 계산하면 $$ O(n^2 * n(n+1)/2) $$ 이고,
전체 시간복잡도는 $$ O(n^4) $$ 입니다.
BOJ 23963 계단 만들기 Small