Layer7 과제 - 코드업 3373번

코드

---

#include <stdio.h>
using namespace std;

int n, a, cant, vst[100000001];

void jagui(){
        n++;
        if(a==1)
                return;
        else if(a%2){
                if(a*3+1<=100000000)
                        if(vst[a*3+1])
                                return;
                        else
                                vst[a*3+1]=n;
                a=a*3+1;
                jagui();
        }else if(!(a%2)){
                if(a/2<n)
                        if(vst[a/2]&&vst[a/2]>=n)
                                return;
                        else
                                vst[a/2]=n;
                a=a/2;
                jagui();
        }else{
                cant=1;
                return;
        }
}

int main(){
        int f, b, max=0, max_num=0;
        scanf("%d %d", &f, &b);
        for(int i=f;i<=b;i++){
                if(!vst[i]){
                        n=0;
                        cant=0;
                        a=i;
                        vst[i]=1;
                        jagui();
                }
                if(n>max&&!cant){
                        max=n;
                        max_num=i;
                }
        }
        printf("%d %d", max_num, max);
}

---

· 일단 처음에 무지성 재귀함수로 풀려고 시도해보았다. 그러나 a와 b의 값에 각각 1과 10000000을 넣어보니 재귀함수의 과다 호출로 인해 세그먼트 폴트 에러가 났다.

· 그 후에 이 문제는 기본적인 재귀함수 문제랑은 다르게 메모이제이션 기법을 사용해야 할 것 같다는 생각이 들었고, 수정의 수정을 거치며 visit 배열을 잘 이용해보려고 노력했다. 첫 시도는 그냥 '배열 크기를 1억 정도로 잡으면 인덱스 에러는 안 나지 않을까?' 라는 생각을 가지고 시도해보았으나, 계속해서 세그먼트 폴트 에러가 났고, 왠지 인덱스를 넘어가는 수가 나올 것 같아 두 번째 시도로 재귀 함수 내에서 예외처리를 해주었으나, 또 세그먼트 폴트가 났다. 그래도 1만까지는 값이 잘 나오는 걸로 유추해보았을 때, 세그먼트 폴트 에러는 함수 과다 호출로 인한 메모리 초과가 원인일 것 같아 main 함수에서 재귀함수를 호출할 때도 예외처리를 해주고, 재귀 함수의 인자를 아예 없애버렸지만 계속 세그먼트 폴트 에러가 났다. 아마 메모이제이션 기법을 사용한 로직을 처음부터 뜯어 고쳐야 할 것 같다.

---