6. 백준 1193 분수찾기 분명 어려운 문제가 아닌데 어렵다 -C 언어

이 지그재그 문제 처음 봤을 때 어떻게 굴러가는지 전혀 이해가 되지 않았다.

정말로 이 문제를 풀수 있나하면서 그림까지 그리고도 이해가 되지 않아 아래에 다시 정렬해본 후에야 이해가 되었다

분모 분자 각각 서로 떨어져서 계산해야 하는데 문자는 홀수까지 켜졌다 1까지 작아지고 다시 그 다음 홀수까지 켜졌다 작아진다.

분자는 1(홀수 최대) -> 1 -> 2 -> 3(홀수 최대) ->2 -> 1 -> 1 -> 2 -> 3 -> 4 -> 5(홀수 최대)이런식이로

분모는 1 -> 2(짝수 최대) -> 1 -> 1 -> 2 -> 3 -> 4(짝수 최대) 이런식으로 늘어나게 된다.

 

또 다른 풀이방법도 물론 있겠지만 아직을 여기까지가 내 한계였다.

 

위의 증명을 토대로 작성한 결과 뭔가가 틀어져서 맞긴 맞지만 애매하게 숫자가 다른 구간이 있어 다시 처음부터 뜯어고쳤다.

 

틀림

#include <stdio.h>

int main()
{
    int x, z=0,cnt=0,mit=2,up=1;
    scanf("%d", &x);
    while(1){ //아래
        z++;
        cnt++;
        printf("밑1.%d\n",cnt);
        if(cnt==mit){
            mit+=2;
            cnt--;
            while(cnt>0){
                printf("밑2.%d\n",cnt);

                cnt--;
                if(z==x){
                    break;
                }
                z++;
            }
        }
        if(z==x){
            break;
        }
    }
    mit=cnt;
    cnt=0;
    z=0;
    while(1){
        z++;
        cnt++;
        printf("위1.%d\n",cnt);
        if(cnt==up){
            up+=2;
            while(cnt>0){
                cnt--;
                printf("위2.%d\n",cnt);
                if(z==x){
                    break;
                }
                z++;
            }
        }
        if(z==x){
            break;
        }
    }
    up=cnt;
    printf("%d/%d",up,mit);
}

위치가 헷갈리지 않게 다시 재배치 해주고 고친 결과 답을 맞추긴 했으나 코드가 조금 무리하게 길어진 느낌이 없잖아 있기 때문에 이후에 좀 더 스택이 쌓이면 이 문제는 다시 재도전 해보고 싶다!!

맞음

#include <stdio.h>

int main()
{
    int x, z=0,cnt=0,mit=2,up=1;
    scanf("%d", &x);
    while(z!=x){ //위
        z++;
        cnt++;
        if(cnt==up && z!=x){ //최대치까지 왔으면 1씩 감소
            up+=2;
            cnt--;
            while(cnt>0 && z!=x){
                z++;
                if(z==x){
                    break;
                }
                cnt--;
            }
        }
    }
    up=cnt;
    z=0;
    cnt=0;
    while(z!=x){ //아래
        z++;
        cnt++;
        if(cnt==mit && z!=x){ //최대치까지 왔으면 1씩 감소
            mit+=2;
            cnt--;
            while(cnt>0 && z!=x){
                z++;
                if(z==x){
                    break;
                }
                cnt--;
            }
        }
    }
    mit=cnt;
    printf("%d/%d",up,mit);
}

 

성공!