dynamic programming
-
[백준] 1562 - 계단 수Algorithm 문제 2019. 6. 30. 20:22
https://www.acmicpc.net/problem/1562 1562번: 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 간단한 dynamic programming 문제이다. dp에 이용되는 숫자의 특징은 2가지다. 수의 마지막에 위치하는 숫자 현재까지 사용된 숫자 현재까지 사용된 숫자의 경우, bitmask를 사용하여 10진수로 변환한다. ex) 2, 4, 5 를 가짐 -> 0000110100(2) -> 52 위 두가지 특징을 가진 계단 수의 개수를 2차원 배열에 저장한다. n-1 길이의 계단 수들로부터 n 길이의 계단 수의 계단 수의 개수를 구한다. 배열을 전부 순회하며 해당 수의 가장 뒷자리에 올 수 있는 수를 추가한 뒤, 이를 n ..