[PS스터디 심화반] 5주차 백준 계단 수

개요

 

백준의 계단 수 문제입니다.

 

 

https://www.acmicpc.net/problem/1562

1562번: 계단 수

 

리뷰와 피드백

 

문제를 해결하면서 느낀 점은 지난 번에 풀었던 외판원 문제와 유사함을 느꼈습니다.

지난 번에 분기점이라 느꼈던 기분을 다시 느낄 수 있었네요. 그 때를 극복하고 문제를 해결해낸 사람과

아직 스스로 해결하진 못한 사람이 나뉘었습니다. 그래도 지난 번과 달리 비슷한 접근이라도 할 수 있었다는 부분에

큰 의미를 두고 꾸준히 나아가 스스로 해결할 수 있게 되기를 바랐습니다.

 

 

 

 

개선 전 / 후   코드 전문

 

#include <iostream>
#include <algorithm>

#define MOD 1000000000

using namespace std;

using ll = long long;

int d[12][102][(1 << 10)];
int n;
ll ans;

int rec(int num, int size, int state){
	
	int &ret = d[num][size][state]; 
	if (ret) return ret;
	if (size == n) {return state == (1 << 10) -1 ? 1 : 0;}

	if (num > 0) ret = (ret + rec(num-1, size+1, state | (1 << (num-1)))) % MOD;
	if (num < 9) ret = (ret + rec(num+1, size+1, state | (1 << (num+1)))) % MOD;
	return ret;
}

int main(){
	cin >> n;
	for (int i = 1; i <= 9; ++i)
		ans += rec(i, 1, (1 << (i)));
	
	cout << ans % MOD;
}

 

 

 

향후 방침, 느낀 점

 

DP 문제에 있어 어려움을 느끼는 사람이 많은 것 같습니다. DP를 해결하는데 있어 직관력과 시야를 더 증진시킬 수 있도록 노력하여야겠습니다.