글 읽기 - [C++] 마지막 0을 입력받을 때의 탈출조건 위치에 따른 메모리초과 발생문제

ljhhasang 2년 전 0

아래 코드를 C++17로 제출시 메모리 초과가 발생합니다. 다른 로직 부분을 살펴보았지만 이상한 점이 보이지 않아 main 함수 내부를 수정해봤습니다.

int main(void) {
    int n;
    while (1) {
        cin >> n;
        if (n==0) break;
        solve(n);
    }
}

위와 같이 main함수를 수정하는 경우 2412KB에 156ms 로 제한조건 내로 맞았습니다!! 로 통과됩니다.

while 문 조건식에 탈출조건을 집어넣는 것과 while 문 내부에 별도로 탈출분기를 추가하는 것의 차이가 무엇인지

알고싶습니다.

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int arr[100000];
ll max_area;

void search(int start, int end) {
    if (start == end) {
        max_area = max(max_area, ll(arr[start]));
        return;
    }
    int mid = (start+end)/2;
    search(start, mid);
    search(mid+1, end);
    
    ll area;
    int l_idx = mid;
    int r_idx = mid+1;
    int mh = min(arr[l_idx], arr[r_idx]);
    while (start <= l_idx && r_idx <= end) {
        area = mh * ll(r_idx-l_idx+1);
        max_area = max(max_area, area);
        if (start == l_idx && r_idx == end) 
            break;
            
        if (r_idx == end ||
            l_idx != start && arr[l_idx-1] > arr[r_idx+1]) {
            l_idx--;
            mh = min(mh, arr[l_idx]);
        } else {
            r_idx++;
            mh = min(mh, arr[r_idx]);
        }
    }
}


void solve(int n) {
    for(int i = 0; i < n; i++) 
        cin >> arr[i];
    max_area = 0;
    search(0, n-1);
    cout << max_area << '\n';
}


int main(void) {
    int n = 1;
    while (n != 0) {
        cin >> n;
        solve(n);
    }
}

zigui 2년 전 1

두 코드의 차이점은 solve(0)을 호출하는지 하지 않는지의 차이가 있어보이고, solve(0)은 재귀 호출을 무한히 많이 하게 되어 스택 오버플로우가 나는 것 같아 보입니다.

추가로, 스택 오버플로우 에러가 메모리 초과로 판정되는 경우도 많이 있습니다.

ljhhasang 2년 전 0

와 생각치도 못했는데 ㅠㅠ 감사합니다!!

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

문제

문제

출처

ICPC

[C++] 마지막 0을 입력받을 때의 탈출조건 위치에 따른 메모리초과 발생문제

ljhhasang 2년 전 0

zigui 2년 전 1

ljhhasang 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말