쉬운 계단수 (1) 썸네일형 리스트형 [백준] 10844 - 쉬운 계단수 아이데이션처음엔 너무 쉽게 2n - 1로 풀었으나, 틀렸습니다!!의 연속이었다.곰곰히 생각해보니까, 이건 저런 단순한 수식이 아니라2차원 DP로 풀어야 하는 문제인 것 같았다.n자리 수에 0 ~ 9의 숫자를 잘 넣으면 되는 문제이고,n자리에 넣을 숫자는 n - 1자리의 숫자의 영향을 받으니까 관계도 확실했다.아래 풀이를 보자사진에서 새로는 0 ~ 9까지 들어갈 수 있는 숫자이고,가로는 n자리수를 의미한다. 어떤 자릿수에 0이 들어갈 수 있는 경우의 수는앞 숫자가 1인 경우 하나 밖에 없다.1 ~ 8가 들어갈 수 있는 경우의 수는앞이 현 숫자보다 1 작거나, 1 큰 경우의 수의 합이다.예를 들어서, 현재 숫자가 8이면앞 숫자가 9이거나 7이어야 되므로 두 경우의 수를 더해주면 된다.그림으로 나타내면 위 브.. 이전 1 다음
