acalgus61   4년 전

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

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포함하고요.. 

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

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

devetude   4년 전

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

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

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

정도가 될 것 같습니다.

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

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

acalgus61   4년 전

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

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

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

답변 감사합니다 :)

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