[C] 백준 1193번 write-up

 

2292번 두 번째 버전느낌의 문제입니다.

 

2292번이 등차수열이라면 해당문제는 조금 더 응용해야 되는 것 같네요

 

문제를 풀기 전, 로직구상을 하고 문제를 풀어보겠습니다.

 

우선 지그재그 순서로 분수가 주어진다고 합니다.

 

그럼 지그재그로 주어지는 분수들을 일렬로 펼쳐보면 다음과 같이 나옵니다.

 

1/1, 1/2, 2/1, 3/1, 2/2, 1/3, ....

 

일렬로 펼쳐진 분수들을 지그재그로 나뉘어 볼게요

 

1번째 열: 1/1

2번째 열: 1/2, 2/1

3번째 열: 3/1, 2/2, 1/3

4번째 열: 1/4, 2/3, 3/2, 4/1

.

.

.

 

이제 규칙성이 보이네요!

 

a/b 형태의 분수들의 범위는 다음과 같이 정의할 수 있습니다.

 

*n은 열의 번호입니다!

1. n이 짝수인 경우

a: 1 ~ n

b: n ~ 1

 

2. n이 홀수인 경우

a: n ~ 1

b: 1 ~ n

 

다 구했으니 이제 코딩해볼게요!

 

#include <stdio.h>

int main() {

    int n;
    int cnt = 1;
    int sum = 0;

    scanf("%d", &n);

    while(sum < n) {
        sum += cnt++;
    }
    cnt--;

    if(cnt % 2 == 0) {
        printf("%d/%d", cnt - (sum - n), cnt + 1 - (cnt - (sum - n)));
    }else {
        printf("%d/%d", cnt + 1 - (cnt - (sum - n)), cnt - (sum - n));
    }
    return 0;
}

 

우선 11번째 줄의 while에서 앞서 로직에서 구해야 할 n값을 얻어줍니다. (cnt 변수가 로직의 n 입니다.)

 

그리고나서 cnt값이 짝수인 경우와 홀수인경우를 다르게하여 출력해주는데 여기서 중요한점이 어떤 값을 출력하는가 입니다.

 

sum 값에는 원하는 n번째 분수가 있는 열의 최대 번호값을 구해줍니다.

 

예를들어서 12번째 값을 구하고싶다면, 12번째 값이 있는 열의 최대 번호는 15가 되겠죠

 

최대 번호 sum 에서 구하고싶은 값의 번호를 빼준 값을 임의로 a로 정할게요.

 

로직에서 구한 열의 번호인 cnt 값에서 앞서 구한 a 값을 빼준다면 원하는 열에서 찾고싶은 분수의 인덱스 위치가 나오게됩니다.

 

제가 적어놓고도 무슨말인지 잘 모르겠는데요

 

디버깅해서 해당 값을 일일이 출력해보시면서, 값의 변화를 트래킹하신다면 굳이 제 설명을 보지않아도 이해되실거에요

 

재밌는 문제였습니다.