글 읽기 - 11025 C++ 메모리초과 질문입니다

0000000000 2년 전 0

우연히 요세푸스 문제에 관한 글을 보게 돼서 그 글에 나와있는 대로 O(N)과 O(KlogN)을 시도해 봤는데 둘 다 메모리 초과가 납니다. 문제가 메모리 제한이 매우 작은 편인 것 같긴 한데 재귀함수로는 풀 수가 없는 건가요?

//O(KlogN)
#include<iostream>
using namespace std;
using ll=long long;
ll f(ll n,ll k){
    if(n==1) return 0;
    if(k==1) return n-1;
    if(k>n) return (f(n-1,k)+k)%n;
    ll c=n/k;
    ll res=f(n-c,k);
    res-=n%k;
    return res<0?res+n:res+res/(k-1);
}
int main(){
    ll n,k; cin>>n>>k;
    cout<<f(n,k)+1;
}
//O(N)
#include<iostream>
using namespace std;
using ll=long long;
ll f(ll n,ll k){
    return n>1?(f(n-1,k)+k-1)%n+1:1;
}
int main(){
    ll n,k; cin>>n>>k;
    cout<<f(n,k);
}

bamgoesn 2년 전 1

이 문제는 N과 K가 최대 5백만입니다. int를 5백만 개 저장하기만 해도 메모리 20MB가 차지됩니다.

재귀함수를 호출하면 재귀의 정보가 스택에 저장이 되는데, 스택의 크기는 몇MB 정도로 많이 작습니다. 때문에 재귀 깊이가 몇백만으로 너무 많아지다보니 스택이 넘친 것으로 보입니다.

0000000000 2년 전 0

for문으로 바꿔서 푸니 맞았습니다. 답변 감사합니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

11025 C++ 메모리초과 질문입니다

0000000000 2년 전 0

bamgoesn 2년 전 1

0000000000 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말