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

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

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

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;

}

2답변

  • 이게 정답일지는 모르겠지만 저라면 재귀함수를 건건이 돌리지 않고 결과 배열만 보고 계산하라고 시킬 겁니다. 파이썬 기준으로 데모를 짜보라고 한다면...

    # 빈 결과배열 하나 만들어주고
    results = {}
    
    # 원래는 빈 결과배열까지 포함해서 클래스화해야 하지만 귀찮으니 생략
    def f(x) :
        # 제0~2항은
        if x < 3 :
            # 그냥 그대로 쓰기로 한다
            to_return = x
        # 3항부터는
        else :
            # 기존 결과배열에 있는 값을 가지고 계산을 해서 쓰기로 한다
            to_return = 3 * results[x-1] + results[x-2] - results[x-3]
        # 이제 위에서 쓰기로 한 그 값을 배열에 찍고
        results[x] = to_return
        # 딱 반환하면 끝
        return to_return
    
    # 50까지 돌려보면 0항부터 49항까지가 찍히고
    for i in range(50) :
        f(i)
    
    # 제49항은 1454890636852453038760761 이라고 하네요.
    print(results)
    

    참고가 되었으면 좋겠네요.

  • #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억짜리 배열을 만들기 어렵기 때문에 %연산자를 활용하면 메모리 절약을 할 수 있습니다.

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

작성한 답변에 다른 개발자들이 댓글을 작성하거나 댓글에 좋아요/싫어요를 할 수 있기 때문에 계정을 필요로 합니다.