[BOJ_2579] 계단 오르기

 

📌 문제 링크: https://www.acmicpc.net/problem/2579

2579번: 계단 오르기

 

✅ 내 풀이(Success) :

계단이 6개 일 때 계단을 오르는 경우의 수

 

🧐 Review:

 처음 문제를 접근했을 때는 모든 경우의 수를 나열해서 규칙성을 찾았다. 여섯 개의 계단을 오르는 경우까지 확인을 해보니 규칙성을 발견했고 점화식을 세울 수 있었다.

문제의 결괏값으로 계단 오르기 게임에서 얻을 수 있는 최고 점수를 반환해야 되는데, 해당 부분은 모든 경우의 수의 점수를 계산하고, 해당 데이터에 max값을 반환해주는 식으로 문제를 풀려고 했지만, 이런 식의 아이디어는 결괏값을 저장하는 dp 배열을 2차원으로 만들어야 해서 코드가 길어지고 복잡해졌다. 이 부분을 좀 더 쉽게 해결하기 위해 다른 사람의 풀이를 확인해보니 max 값을 결과 값을 반환하는 타이밍에 구하는 게 아니라 각 계단마다 max 값을 구하는 풀이를 이용하고 있어서 해당 아이디어를 코드에 적용하니 좀 더 깔끔한 코드로 문제를 해결할 수 있었다.

 

🚩 Idea:

 - 규칙성을 찾기 위해 계단이 하나인 경우부터 시작해서 계단을 하나씩 늘려가며 계단을 오르는 경우의 수를 모든 경우의 수를 찾는다.

 - 해당 경우의 수들은 이전 항과의 관련성이 있는지 확인해보고, 규칙성을 통해 점화식을 세운다.