bbyu   2년 전

안녕하세요. 1463번 1로 만들기 문제를 풀던 도중, 맞기는 하였으나 DP로 문제를 풀다가 궁금한 것이 생겨 질문 올립니다.

먼저 AC를 받은 코드는 for문을 사용하여 차곡차곡 쌓아간 방식이고,

틀린 코드는 solve라는 함수를 사용한 코드입니다.

만약 arr[x] 에 값이 존재할 경우, 해당 값을 리턴하고 존재하지 않을 경우 3, 2 로 나누어지는 경우, 1을 빼는 경우의 함수를 다시 호출하도록 만들었습니다.

80000까지의 값의 경우 동일합니다만, 90000을 입력하였을 경우, solve함수를 활용한 경우에 답이 나오지 않고 중간 디버깅 과정에서 튕기는 것을 확인하였습니다.

visual studio 로 디버깅 했을 경우 stack overflow 가 뜨면서 실행이 되지 않고, codeblock으로 디버깅했을 경우, 중간에 함수 실행 시 멈추는 것을 보았습니다. arr는 두 코드 모두 동일한 것을 쓰기 때문에 배열 문제는 아닌 것 같고, solve 함수가 stack에 쌓이면서 문제가 뜨는 것 같기는 한데, 혹시 왜 이렇게 뜨는지 이유를 알 수 있는지 궁금합니다.

읽어주셔서 감사합니다. 좋은 하루 보내세요 :)

djm03178   2년 전

가령 100만이 입력되었다면 500001을 접근해가는 유일한 경로는 solve(x - 1)이 50만번 재귀호출되는 방법 뿐입니다. 이 정도 재귀호출이면 일반적으로 스택이 감당하지 못합니다.

bbyu   2년 전

/2보다 큰 값은 그렇게 가는 수밖에 없겠네요. 50만번이 호출될거라고는 생각 못했습니다. 그러면 값이 클 때는 재귀적으로 호출하는 함수는 지양하는게 좋겠네요. 시간 내 좋은 내용 알려주셔서 감사합니다. 오늘도 즐거운 하루 되세요!

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