반응형
동적 프로그래밍
-
BOJ) 쉬운 계단 수알고리즘/백준 2020. 7. 6. 18:27
쉬운 계단 수 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 문제 제목은 쉬운 계단 수 인데, 어렵다.. ㅋㅋㅋㅋ DP 문제를 푼지 오래된 것 같아서 DP 문제를 선택해봤다. 우선 2차원 배열을 사이즈에 따라 생성하는 것 까지는 해놓고 생각을 했다. n자리 수 때, 0~9 숫자가 몇 번 쓰이는지 저장을 해야 풀 수 있는 문제인가 생각을 해보았다. 한 20분정도 생각했는데 이 방법은 아니었다. 다른 저장 방법은 없을까 고민했지만 떠오르지 않았다. 위의 생각에 빠져서 해당 숫자에서 -1 , +1 사이에 있어야 하는 것을 간과한 것이다.. 그래서 질문하기 게시판을 참고했다. 코드가 있는 질문들은 과감하게 넘기고 점화식을 물..