Vacuous Truth1 [백준] 10844 - 쉬운 계단 수, C++ https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 본 문제는 인접한 모든 자릿수의 차이가 1이 나는 수를 계단 수의 경우의 수를 구하는 문제다. 큰 문제를 작은 문제에서 구할 수 있기 때문에 DP로 풀 수 있다. i자리 수 중 j로 끝나는 경우의 수는 i-1자리 수 중 j+1, j-1의 경우의 수를 더한 값이다. 그러나 끝자리가 0인 경우는 1, 9인 경우는 8 밖에 없다. 따라서, 점화식을 d[i][j] = d[i-1][j+1] + d[i-1][j-1]로 정의하고, d[i][0] = d[i-1][1], d[i][9] = d[i-1][8]로 예외 처리를 하면 .. 2020. 1. 11. 이전 1 다음