쉬운 계단 수

[python3] 백준 10844 풀이 ( 쉬운 계단 수, 다이나믹 프로그래밍, 이차 배열)

이번 문제 너무 어려웠다. 이것저것 해보다가 결국 해설을 봐버렸지만 그냥 외워서 체득시켜 놓아야 겠다. 솔직히 이거 못풀었다. 그래서 해설을 보고 이해하고 풀게 되었다. 처음에는 노가다로 갯수를 구해보았다. 9, 17, 32, 61까지 구했고 먼가 규칙이 있는듯 했지만 결과만으로는 규칙을 찾을 수 없었다. 그래서 끝자리를 배열에 넣어 개수를 확인하는 방식을 사용해보았다. 그러나 이렇게 풀면 시간초과가 났다. 알고보니 배열을 2차원 배열을 만들어 각 숫자별 개수를 저장하여 푸는 방법이 존재했다. 예를 들어 끝자리가 가능한 숫자는 0~9까지 이다. 따라서 이에 대한 배열을 만든다. 그리고 N=1일때 가능한경우에 1을 채워준다. 0은 시작부분에 나올수 없기 때문에 0이 되고 나머지는 가능하므로 1을 채울 수 ..

백준 10844 풀이 (쉬운 계단수, 다이나믹 프로그래밍)

이번에는 쉬운 계단수를 풀어본다. 역시 노래를 안들으면서 풀었더니 어찌저찌 풀렸다. 앞으로 알고리즘 풀때 노래 안들어야겠다..... 일단 문제를 보면 별게 없다. 처음 시작부터 계단을 하나씩만 오고갈 수 있고 이렇게 나올 수 있는 경로의 총 합을 구하면된다. 그럼 대강 계단이 어떻게 경로가 생성되는지 구해본다. 그림을 그려보면 이전에 사용된 N값을 이용하여 다음 N+1의 계단에 총 수를 알 수 있다.(0에서 값이 조금 다르듯이, 9에서도 값이 다르기 때문에 이 부분을 염두해 두고 코딩해야한다.) 따라서 수의 길이에 따른 시작 계단별 수를 저장하기 위해 2차원 배열을 선언하고 차곡차곡 쌓아가면서 다음 수에서의 계단별 수를 저장하면 된다. 마지막에는 구하고자 했던 N값에 해당 되는 값에서 0으로 시작하는 경..