c언어백준10844번쉬운계단수1 C언어 백준 10844번 쉬운 계단 수 문제 풀이 계단 수는 자리 차이마다 1의 차이를 가지고 있는 수이다. DP에서 중요한 점은 배열로 풀 때 - DP의 인덱스는 어떤 값을 넣을 것이고 - 그 배열 안에는 어떤 값이 들어갈 지 - 점화식을 어떻게 세울 것인지 인 것 같다. 이번 문제도 마찬가지로 인덱스 값을 어떤 값을 넣지와 배열 안의 값이 어떤 값이 들어갈 지가 중요하였다. DP[몇 번째 수][자릿수] = 총 개수 로 정의할 수 있다. 이 때, 바로 옆 숫자 대비 1씩 다르다. 왼쪽부터 n번째 자릿수는 n-1번째 자릿수 값+1과 n-1번째 자릿수 값-1의 개수에서 오기 때문에 둘을 더하면 된다. 예를 들어 3번째 자릿수 3인 경우, 2번째 숫자 2의 개수와 2번째 숫자 4의 개수를 더한 개수가 된다. 다만, 0과 9는 올 수 있는 경우가 .. 2022. 6. 9. 이전 1 다음