[백준] #10844 쉬운계단수

개요

---

동적계획법을 사용했다.

이 문제를 풀면서 많은 것을 배울 수 있었다.

 

1. 재귀로 너무 많이 돌리거나, cache[10000+1]이런식으로 커지면 메모리 초과가 난다..

2. 메모리 초과가 나면 bottom-up방식을 생각해보자

3. 재귀 대신 for문 사용도 고려해보자

4. 어차피 피보나치처럼 n-2, n-1만 쓸거면 캐시를 100개씩 만들필요없고 3개만 만들어도 된다!

5. INT말고 LONG LONG쓰는거 주의하자

6. MOD연산도 주의하자

 

 

 

기존에는 맨날 재귀로만 돌려서 어떻게 bottom-up과 for문을 사용하는지 몰랐었는데

이 문제를 풀고 알게됐다.

재귀함수에 쓸 파라미터 수를 고려하여 cache나 저장할 변수를 만들어서 사용하면 된다.

 

 

코드

---

기존에 썼던 방법 (재귀):

for문으로 bottom-up

 

 

 

코드 복사용

 

 

long long cache[100][10];
long long solve(int n, int i){
    if(n == 1) return 1;
    long long& ret = cache[n][i];
    if(ret != -1) return ret;
    
    if(i == 9) return ret = solve(n-1, i-1) % MOD;
    else if (i==0) return ret = solve(n-1, i+1) % MOD;
    else return ret = (solve(n-1, i+1)%MOD + solve(n-1, i-1) % MOD) % MOD;
}

 

long long solve2(int n){
    //어차피 n-1만 참고하기때문에
    //현재꺼, 바로 이전꺼만 저장하면 된다
    long long cache[2][10] = {{0,0,0,0,0,0,0,0,0},{1,1,1,1,1,1,1,1,1,1}};
    
    for(int i = 2; i<=n; i++){
        int flag = i%2;
        for(int j = 0; j<=9; j++){
            if(j==0) CUR = UP;
            else if(j==9) CUR = DOWN;
            else CUR = (UP %MOD + DOWN %MOD)%MOD;
        }
    }

    long long answer = 0;
    int flag = n %2;
    for(int j = 1; j<10; j++){
        answer = answer + CUR % MOD;
        answer %= MOD;
    }
    return answer;
}

 

 

참고

---

 

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

10844번: 쉬운 계단 수