5626번: 제단 (acmicpc.net) 5626번: 제단 첫째 줄에 가능한 제단의 수를 1,000,000,007로 나눈 나머지를 출력한다. www.acmicpc.net 시간 복잡도: O(N * H/2) 알고리즘: DP 말이 꼬여있어서 어렵습니다. 하지만 보면, i번째 제단과 i-1번째 제단 혹은 i+1번째 제단의 차이는 1 이상 날 수 없습니다. 이는 계단 수 문제랑 비슷한데, 변형되었습니다. 조건은 다음과 같습니다. 시작은 0이여야 합니다. 따라서 1번째 제단의 입력이 0 혹은 -1이 아니라면, 바로 0을 출력합니다. 끝 또한 0이여야 합니다. i번째 제단이 -1이 아닌 경우 i 빼고 모든 값을 0으로 초기화합니다. i번째 제단을 j로 설치하는 경우의 수는 i-1번째를 j, j+1, j-1로 설치하..