7-F 시간초과 질문

작성한 질문수 10

1

안녕하세요 김준님 ㅎㅎ

대부분 잘 짜셨는데요 ㅎㅎ

dp[1]의 값 설정, 메모이제이션 관련 로직을 수정해야 합니다.

제가 한번 다듬어봤는데요 ㅎㅎ 참고부탁드립니다.

#include <bits/stdc++.h>
using namespace std;

using int64 = long long;

int64 n;
int64 dp[1'000'004];
const int64 MAX = 987654321;

int64 Solution(int64 n)
{
    if (dp[n] != MAX) return dp[n];

    if (n == 1) return 0;

    int64 &count = dp[n];

    if (n % 3 == 0)
        count = min(count, Solution(n / 3) + 1);

    if (n % 2 == 0)
        count = min(count, Solution(n / 2) + 1);

    count = min(count, Solution(n - 1) + 1);

    return count;
}

void Print(int64 n)
{
    if (n == 0)
        return;

    cout << n << " ";

    if (n % 3 == 0 && dp[n] == dp[n / 3] + 1)
        Print(n / 3);
    else if (n % 2 == 0 && dp[n] == dp[n / 2] + 1)
        Print(n / 2);
    else if (n - 1 >= 0 && dp[n] == dp[n - 1] + 1)
        Print(n - 1);
}

int main()
{
    cin >> n;

    fill(dp, dp + 1'000'004, MAX);
    dp[1] = 0;

    int64 result = Solution(n);
    cout << result << '\n';

    Print(n);
    cout << '\n';

    return 0;
}

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

0

안녕하세요, 인프런 AI 인턴입니다. 김준님.

재귀를 사용한 코드가 시간 초과가 나는 이유는 재귀 호출의 특성 때문입니다. 재귀 호출은 함수 호출 스택에 많은 부담을 주며, 특히 많은 호출이 일어나는 경우 오버헤드가 발생해 성능 저하를 초래할 수 있습니다. 반면에 반복문은 이러한 오버헤드가 없어 더 효율적입니다.

아래 링크에서 유사한 문제에 대한 답변을 확인하실 수 있습니다:

• 7-A 질문 - 레퍼런스를 사용하지 않으면 시간초과의 원인이 될 수 있습니다. 자세히는 메모이제이션 없이 재귀를 사용한 경우 시간 초과가 발생할 수 있습니다.
  
• 1-L 이중 for 문으로 풀면 시간초과가 납니다(코드 포함) - 시간 초과 해결을 위한 최적화 방법을 설명합니다.
  

이 문제와 다른 비슷한 질문을 통해 더 자세한 최적화 방법과 접근법을 배울 수 있습니다.

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.