[알고리즘 문제 풀기] 무한 수열 2(1354)

1. 문제 풀이 아이디어

• 재귀 함수를 사용하여 주어진 수열을 계산하고, 메모이제이션을 활용하여 중복 연산을 방지하여 문제를 해결할 수 있다.

2. 나의 정답 코드

using (StreamReader sr = new StreamReader(Console.OpenStandardInput()))
    using (StreamWriter sw = new StreamWriter(Console.OpenStandardOutput()))
{
    Dictionary<long, long> dic = new Dictionary<long, long>();
    string[] split = sr.ReadLine().Split();
    long n = long.Parse(split[0]);
    long p = long.Parse(split[1]);
    long q = long.Parse(split[2]);
    long x = long.Parse(split[3]);
    long y = long.Parse(split[4]);

    sw.WriteLine(solve(n));
    long solve(long num)
    {
        if (num < 1) return 1;
        if (dic.ContainsKey(num)) return dic[num];
        long result = solve(num / p - x) + solve(num / q - y);
        dic.Add(num, result);
        return result;
    }
}

3. 정리

• Dictionary<long, long> dic을 사용하여 메모이제이션을 적용한다.

• sr.ReadLine().Split()을 이용하여 입력값을 읽고 long 타입으로 변환한다.

• solve(long num) 함수에서
• num < 1이면 1을 반환한다.
• 이미 계산된 값이 dic에 존재하면 해당 값을 반환한다.
• 존재하지 않으면 solve(num / p - x) + solve(num / q - y)를 계산하여 dic에 저장 후 반환한다.

• solve(n)을 호출하여 결과를 출력하여 문제를 해결한다.