CHULMING   6년 전

단순하게 제곱 수를 빼나가며 재귀호출을 하는 식으로 작성하였습니다.

vs에서는 5000이상 입력 시 돌아가지 않고, dev에서는 9999까지만 돌아가네요.

제출 해보니 예상대로 런타임에러가 나왔습니다.


1) 수가 5000일 때 1*1을 5000번 빼면서 재귀호출이 너무 많이 발생해서 스택 오버플로우로 런타임 에러가 나는건가요?

2) 접근부터가 잘못된 것 같은데, 이런 류의 문제는 어떻게 접근해야 하나요?

haja   6년 전

여기 올려주신 코드는 답이 정상적으로 나오구요. 이 문제에서는 문제 없지만 

if(dp[n] != 0) return dp[n];
if(n < 0) return INF;
if(n == 0) return 0;
여기서  두 번째줄에서 범위 벗어나는지 체크하는걸 먼저하셔야 dp[n]이 이상한곳에 접근하지 않아요.
실제 제출했던 소스가 런타임 에러 난거는 

for(j=1; arr[j]<=n ;j++){
  int temp = recur(n-arr[j]);
  cot = MIN(cot,temp);
}

여기서 루프를 n까지 돌아서 그래요

CHULMING   6년 전

정말 감사합니다!

가독성 있에 코드를 올려야 보기 편하실 듯 해서 다듬어서 올리다 보니 질문이 이상해졌네요....


말씀하신대로

if(dp[n] != 0) return dp[n];
if(n < 0) return INF;
if(n == 0) return 0;

이 부분 수정해서 다시 제출해서 웹에서는 정답을 받았는데,

여전히 vs, dev에서는 100000을 입력하면 돌아가지 않는데, 이유가 무엇일까요?

haja   6년 전

컴파일 할때 스택 제한을 낮게 잡아둬서 그래요. 보통 온라인 저지는 256MB 정도 잡을거에요.

CHULMING   6년 전

감사합니다! 다 해결됐네용

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