알고리즘 문제 질문드립니다.

조회수 142회

아래와 같은 문제를 접했는데 풀이 방법을 모르겠습니다.

일단 이런 점화식이 있습니다.

f(n) = 3f(n-1) + f(n-2) - f(n-3), f(0) = 0, f(1) = 1, f(2) = 2

그리고 주어진 n(1~1억)에 대해 그냥 f(n)값을 출력하는게 문제입니다;;

선형적으로 더해서 풀었을 때 당연하지만 1억 대입하면 시간초과가 나와서 다른 방향을 생각해봤는데 떠오르질 않네요.

크게 생각해본건 두가지입니다.

1) 점화식을 수학적으로 변형시켜서 다른식을 뽑아내는것.

2) 하위점화식으로 변환해서 f(2), f(1), f(0)에 대한 식으로 만드는것. 하지만 이러면 어차피 계수가 3의 지수식들 합으로 나올건데 연산량에 차이가 있을까 싶어서 깊게 안들어가봤습니다.

그런데 둘다 딱히 답으로 이어지는것 같지가 않네요. 연산량을 어떻게 줄일 수 있을지 조언 주시면 감사드리겠습니다. 아래는 제가 선형적으로 푼 코드인데 기억으로 복원한거라 정확하지 않을 수도 있습니다. 양해해주시면 감사드리겠습니다.

int solution(int n) { if (n == 1) return 1; if (n == 2) return 2;

unsigned fm3;
unsigned fm2 = 0;
unsigned fm1 = 1;
unsigned f = 2;

int ans;
for (int i = 3; i <= n; i++) {
    fm3 = fm2;
    fm2 = fm1;
    fm1 = f;

    f = (3 * fm1)%= 100000007 + fm2 - fm3;
    ans = f % 100000007;

    if (fm2 >= 100000007 && fm1 >= 100000007 && f >= 100000007) {
        fm2 %= 100000007;
        fm1 %= 100000007;
        f %= 100000007;
    }

}

return ans;

}

1 답변

  • #include <cstdio>
    
    int solve(int);
    
    int main(void)
    {
        int n;
        scanf("%d", &n); // 0이상의 정수
    
        printf("%d\n", solve(n));
        return 0;
    }
    
    int solve(int n)
    {
        if (n <= 2)
            return n;
    
        int idx = 0;
        long f[4] = {0, 2, 1, 0}; //f[idx] = f(n) // f[(idx + 1) % 4] = f(n-1) // f[(idx + 2) % 4] = f(n-2) // f[(idx + 3) % 4] = f(n-3)
    
        for (int i = 3; i <= n; i++)
        {
            f[idx] = (3 * f[(idx + 1) % 4] + f[(idx + 2) % 4] - f[(idx + 3) % 4]) % 1000000007;
            if(f[idx] < 0) // 항상 양수만 저장
               f[idx] += 1000000007;
    
            idx = (idx + 3) % 4; //다음 연산에서, 지금의 f(n-3)는 쓰지 않는 값이므로 f(n)을 저장하는 용도로 씀.
        }
    
        return idx >= 3 ? (int)f[idx - 3] : (int)f[idx + 1]; // 마지막 for문에서 끝에 idx = (idx + 3) % 4 를 해줬기 때문에 한번 되돌려야함. 이해 안가면 (n = 3)일때 생각해보기
    }
    

    DP문제입니다(Memoization). 하지만 크기가 1억짜리 배열을 만들기 어렵기 때문에 %연산자를 활용하면 메모리 절약을 할 수 있습니다.

답변을 하려면 로그인이 필요합니다.

Hashcode는 개발자들을 위한 무료 QnA 사이트입니다. 계정을 생성하셔야만 답변을 작성하실 수 있습니다.

(ಠ_ಠ)
(ಠ‿ಠ)

ᕕ( ᐛ )ᕗ
로그인이 필요합니다

Hashcode는 개발자들을 위한 무료 QnA사이트 입니다. 계정을 생성하셔야만 글을 작성하실 수 있습니다.