[C] 더블릿 4단계_ 최대수연결 문제

2번째 과제인 최대수 연결문제... 개인적으론 정말 어려웠습니다..ㅋㅋㅋㅋㅋ헣 최대수 연결문제는 다음과 같습니다.

 

두 양의 정수가 주어질 때 두 수의 길이는 다음과 같이 약속

• 앞수에서 뒤수를 빼가는 과정을 반복.
• 뺀 값이 음수이면 종료 아니면 반복

예를 들어 , 두 수가 5 3 이면

5 3 2 1 1 0 1

5 3 의 길이는 이어지는 수의 개수 7 .

n 이 입력으로 주어질 때 두 번째수를 1 , 2 , .. n 으로 줄 때 최대 길이를 구하는게 문제이다.

n 이 5 이면

• 5 1 4
• 5 2 3
• 5 3 2 1 1 0 1
• 5 4 1 3
• 5 5 0 5

최대 길이는 5 3 일 때 7 이다.

입력

n 은 1000 이하의 자연수이다.

출력

최대 길이를 출력한다.

입출력 예

입력

5

출력

7

어제 소인수분해 문제를 푼 경험을 바탕으로 하나의 숫자를 정해 자세히 분석하였으나 빨리 이해되지는 안더군요ㅜㅜ 그래도 내가 

휴리스틱으로 쉽게 계산한 것을 하나하나 정리하여 그것을 코드로 정리하면 문제를 풀 수 있다는 진리를 바탕으로 다음과 같이 첫 코드를 짰습니다.

 

#include <stdio.h>

int main(){

        int a, b, temp, x, y = 1, MAX = 0;

        long double c[1000][10000] = { 0 }; //2차원배열로 각 경우의 길이 저장.

        int i = 0, j = 0;

        scanf("%d", &x); 

        a = x;

                 for (i = 0; i < x; i++){

                         j = 0;

                         b = y;

                         while (a - b >= 0){

                                  c[i][j] = a - b;

                                  temp = a;

                                  a = b;

                                  b = temp - b;

                                  j++;

                         }

                         y++;

                 }

        MAX = sizeof(c) / sizeof(c[0]); //행렬 c의 row의 원소 갯수 구하기.

        for (i = 1; i < x; i++){

                 if (sizeof(c) / sizeof(c[i - 1]) < sizeof(c) / sizeof(c[i])){

                         MAX = sizeof(c) / sizeof(c[i]);

                 }

        }

        printf("%d", MAX);

        return 0;

}

 

하하... 보이시는대로 쓸데없이 복잡하기만하고 돌아가지도 않는 똥을 창조하였습니다.. ㅋㅋㅋ 그러나 이렇게 만드는데도 몇시간 걸렸다는게

함정.. 하하

완전 열심히 만들었는데 이름은 겁나 많이 들었지만 개인적으론 처음보는 stackoverflow 때문에 아무리 코드를 수정해도 빌드도, 당연히 

디버깅도 안되서 2시간 반이 지나서야 미련을 버리고 코드를 싹 밀어버렸습니다ㅜㅜ 

(대체 왜그런걸까요? 심심할 때 stackoverflow 구체적으로 찾아봐야지)

 

절망은 잠시 뒤로한체 후배들과 제 집에서 맜있는 카레 밥과 카레 라면까지 4명서 총 8인분을 먹고나니 다시 시작할 힘이 생기더군요.

전 코드를 밀고 다시 천천히 생각해보니 꼭 2차원 배열을 쓸 필요는 없다고 생각이 들더군요. 그래서 다음과 같이 코드를 짰습니다.

 

 

#include <stdio.h>

int main(){

        int a, b = 1, c;

        int x = 0, y, temp = 0, count = 0, MAX[1000], M;

        scanf("%d", &x);

        MAX[0] = 0; //y가 1부터 시작하기 때문에 딱히 값이 들어갈 경우가 없어서 따로 초기화.

        a = x;

        c = a - b;

        for (y = 1; y <= x; y++){

                 c = x - y;

                 a = x; //while문 안에서 바뀐 a 값 초기화

                 b = y; //while문 안에서 바뀐 b 값을 y에 맞춰 하나씩 증가하게 함.

                 count = 0; //count 초기화를 해 y가 바뀔때마다 다시 셈.

                 while (c >= 0){

                         count++;

                         temp = a;

                         a = b;

                         b = temp - b;

                         c = a - b;

                 }

                 MAX[y] = count; // 각 경우의 길이들을 배열에 담아줌.

                 if (MAX[y] > MAX[y - 1]){  //배열의 원소들을 비교해 제일 큰 값만 저장.

                         M = MAX[y];

                 }

        }

        printf("%d", M+2); //문제가 처음 입력받는 수와 y를 포함하여 세기 때문에 +2를 해줌.

        return 0;

}

결과는??????????????

하하ㅏㅎ하하하하하하ㅏ핳하ㅏ핳하하하하하ㅏㅎ하하하ㅏ하 정말 너무 기뻤습니다 하하하ㅏㅏㅜㅜㅜㅠㅠㅜ

오늘 하루종일 고민했던 문제를 혼자힘으로 풀다니ㅜㅠㅜㅜㅜㅜ으어어ㅜㅜㅜ 행복합니다ㅠㅜㅜ

 

2번 문제를 풀면서 뭔가 이런 방향으로 하는게 맞는 것 같은데 답이 애매하게 안나온다면, 한단계 씩 디버깅을 꼭꼭꼭꼭!!!!

하자는 교훈을 얻었습니다. 여태까진 겁나 쉬운 문제밖에 안풀어서 (물론 이것도 그런축에 속하는 것 같긴 하지만..ㅠ) 디버깅을 따로 안써도 해결됬는데

이번문제는 정말 디버깅의 도움을 많이 받았습니다. 

결국 2번 문제 결론 ------- 디버깅 차냥해~