글 읽기 - 통과는 됐는데 반례를 찾아버렸습니다,,,

stajw 4년 전 1

top-down 방식으로 구현해서 제출해서 통과까지 받았는데

제가 호기심으로 999999를 넣어보니깐 Segmentation fault가 나옵니다ㅠㅠ

제 코드에 문제가 없다고 생각해서 제출해서 통과까지 받은건데 이런 오류가 나니깐 당황스럽네요,,,

혹시 제가 온라인 컴파일러로 돌려서 이런 에러가 나오는걸까요??

#include <iostream>
using namespace std;

int arr[1000001];

int lesss(int a, int b){
    if(a<b) return a;
    else return b;
}

int solve(int n){
    int min = 1000001;
    if(n==1){
        arr[1] = 0;
        return 0;
    }
    else if(n==2){
        arr[2] = 1;
        return 1;
    }
    if(arr[n] > -1) return arr[n];
    else{
        if(n%3==0){
            min = lesss(min, solve(n/3) + 1);
        }
        if(n%2==0){
            min = lesss(min, solve(n/2) + 1);
        }
        min = lesss(min, solve(n-1) + 1);
        arr[n] = min;
        return arr[n];
    }
}

int main(){
    int n;
    cin >> n;
    fill_n(arr,1000001,-1);
    cout << solve(n);
    return 0;
}

ho94949 4년 전 1

n에 999999를넣을경우,재귀호출이 상당히 깊은 단계 까지 들어갑니다.

그래서 스택 메모리 초과가 일어나게 되는 것 같은데, 사용하는 온라인 컴파일러 서비스가 스택 메모리 제한이 충분치 않은것 같습니다,

stajw 4년 전 0

감사합니다!!

그렇다면 제 코드에는 문제가 없다고 생각해도 될까요??

ho94949 4년 전 2

네, 스택 메모리가 여유로운 상황 (백준 온라인 저지 등) 에서는 문제가 없어요

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

문제

문제

출처

ICPC

통과는 됐는데 반례를 찾아버렸습니다,,,

stajw 4년 전 1

ho94949 4년 전 1

stajw 4년 전 0

ho94949 4년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말