글 읽기 - 재귀를 이용해서 푸는데, 런타임 에러

acalgus61 7년 전 0

코드는 재귀를 이용해서 작성했습니다.

permuteSum에서 i는 시작점, curL는 현재 길이, sum 은 현재 단계에서 합입니다.

N/L * L = N이므로, 답의 시작점은 항상 N/L보다 작을 것이므로 초기값으로 N/L을 주었습니다.

재귀 함수에 대해 설명하자면

기본케이스는 길이가 100 이상 이거나 시작점이 음수일때이고

sum이 N보다 작으면, 길이는 그대로, 시작점을 -1 작은쪽으로 이동합니다 (시작점: i-1, 길이: curL)

sum이 N보다 크면, 길이를 +1늘리고, 시작점을 -1 작은쪽으로 확장시킵니다 ( 시작점: i-1, 길이: curL+1)

답에 0포함하고요..

저랑 같은 방식으로 푸신 분 있나요?

런타임에러가 나는데, 반례를 찾아주신다면 감사하겠습니다 ㅠ

import java.util.Scanner;

public class Main{

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int L = sc.nextInt();
		int initialSum=0;
		for(int i=N/L; i<N/L+L; i++)
			initialSum +=i;
		
		int start = permuteSum(N/L, L, initialSum, N);
		StringBuilder sb = new StringBuilder();
		int sum =0;
		if(start<0) sb.append(-1);
		while(start>=0 && sum<=N){
			sb.append(start++ +" ");
			sum +=start;
		}
		System.out.println(sb.toString());
	}
	public static int permuteSum(int i, int curL, int sum, int targetSum){
		if(curL>100 || i<0) return -1;
		if(sum == targetSum) return i;
	//	if(sum+(i-1) == targetSum ||sum+(i-1)-(i+curL-1)==targetSum) return i-1;
		if(sum>targetSum){
			return permuteSum(i-1,curL, sum+(i-1)-(i+curL-1), targetSum);
		}else{
			return permuteSum(i-1,curL+1, sum+(i-1), targetSum);
		}
		
	}
}

devetude 7년 전 0

코드를 정확하게 읽어보지는 않았지만, 올려주신 소스 코드에서 런타임 에러가 발생할만한데를 짚어보자면,

1. 재귀 사용 : 호출 수(깊이)가 너무 깊어서 할당되어있는 스택을 초과해 오버 플로우가 발생한 경우

2. 나누기 연산에서 어떤 수를 0으로 나눈 경우

정도가 될 것 같습니다.

이 문제를 풀어보지는 않았지만 읽어보니, 투 포인터 문제 같은 느낌이 강하게 드는데, 투 포인터 알고리즘 풀이 방법으로 접근해 보시면 좋을 것 같습니다.

저도 풀어 본 이후에 다시 답변을 드리겠습니다.

acalgus61 7년 전 1

스택오버플로우 에러 맞네요 ㅠ ㅠ

while문으로 바꿔서 맞췄습니다

제가 푼 방법도 투포인터와 거의 흡사한 ( 수열의 끝 포인터 대신 길이를 바꿀뿐....) 것 같네요.

답변 감사합니다 :)

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

문제

문제

출처

ICPC

재귀를 이용해서 푸는데, 런타임 에러

acalgus61 7년 전 0

devetude 7년 전 0

acalgus61 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말