글 읽기 - 런타임 에러 ...

sgy8971 6년 전 0

Algorithm은

25114라면

[1,1] [2,5] + [1,2] [3,5]

이런식으로

구간을 나눠 구하려고 했습니다.

1) 10줄 코드가 들어간 이유

[3,5]일경우

17줄에서

arr[3] * 10 + arr[4] < 27이기 때문에

(= arr[3] * 10 + arr[4]가 만드는 경우의 수는 무조건 1개다 = '11' )

==> cnt = ( cnt + 1 * solve(5,5) ) % mod

ex) 1개( '11'이라는 암호코드가 있기 때문에) x [ arr[5,5]가 만드는 경우의 수 ]

==> 이런 경우 10줄 코드가 필요 없음

[3,4]일경우

right - left = 1 일경우

= 무조건 생기는 경우의 수는 1개다

= 그런데 코드상 solve(left+2, right)이기 때문에 10줄 추가

런타임에러가 어디서 나는 걸까요 ㅠㅠ

알려주시면 정말 너무 감사하겠습니다

#include <iostream>
#define mod 1000000
using namespace std;

string tmpStr;
int arr[5005];
int dp[5005][5005];

int solve(int left, int right){
    if( left > right ) return 1;
    if( left == right) return dp[left][right] = 1;
    if( dp[left][right] != 0) return dp[left][right];
    
    int cnt=0;
    
    cnt = ( cnt + 1 * solve(left + 1 , right) ) % mod;
    if( arr[left] * 10 + arr[left+1] < 27)
        cnt = ( cnt + 1 * solve(left + 2, right) ) % mod;
    
    return dp[left][right] = cnt;
    
}


int main(){
    cin >> tmpStr;
    int size = tmpStr.size();
    
    if( tmpStr == "0") {
        cout << "0" << endl;
        return 1;
    }
    
    for(int i=1; i<=size; i++){
        arr[i] = tmpStr[i-1] - '0';
    }
    
    int result;
    result = solve(1, size);
    cout << result << endl;
    
    return 0;
}

joonas 6년 전 0

음, 개인 번호는 지우시는 게 좋을것 같아요 ㅎㅎ

중간에 "0" 이면 return 1 을 하신 이유가 있나요? 정상 종료는 return 0 입니다.

upple1 6년 전 0

dp사이즈가 너무 커서 그런 것 같은데요. 메모리가 너무 커도 런타임 에러 나는 경우가 있어요

seico75 6년 전 0

5000개가 다 1인 경우를 보면 재귀가 5000을 들어가야 합니다. Stack Overflow 나지 않을까요?

재귀로 할 경우 (문자열 길이가 길지 않을 경우) upple1 님 말씀처럼 dp 가 필요 이상으로 큰 것 같은데, 2차원배열일 필요는 없을 것 같습니다.

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

문제

문제

출처

ICPC

런타임 에러 ...

sgy8971 6년 전 0

joonas 6년 전 0

upple1 6년 전 0

seico75 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말