[C++] 1193번: 분수찾기

먼저, 분수의 형태는 사실상 배열의 rol. column을 /로 구분한 형태라서 분수는 크게 중요치않다.

분수 배열의 "순서"만 놓고 따질때 저 초록선대로 그룹을 지어보면 다음과 같다.

1, 2 3, 4 5 6, 7 8 9 10, ...

여기서 i = 1으로 놓고 그룹의 시작값만 보면...

1, 2, 4, 7 ...

이 시작값의 차이는 1, 2, 3 이라는 규칙을 가진다.

이제 할 것은 간단하다. 입력값 n에 대해서 배열 시작값(1,2,4,7..)과 반복적으로 비교하다가 입력값 n이 배열 시작값보다 작아지는 때가 온다면 여기서 위치를 추적하는 방식이다.

 

예를 들어, n으로 9가 주어졌다.

1, 2, 4, 7, 11... n과 비교하다가 11에서 조건을 달성하게 된다.

1	2	6	7	15
3	5	8	14
4	9	13
10	12
11

11에서 9의 위치를 추적하는 것은 11, 10과 같은 꺾이는 구간이 있기도 해서 그냥 쭉 구하기만 하면 되는 이전값 7에서 찾기로 했다.

이렇게 위치를 추적하느니,

이전값에서 이렇게 추적하겠다는 얘기.

이전값을 찾는건 진짜 별 거 없다.

위의 예에서는 i = 5, 시작값 check = 11에서 조건을 달성하게 되는데,

i에서 1을 빼고, check에서 i를 빼면 된다. 즉 i=4를 만든 후, check = check(11) - i(4) = 7

(위와 같이 구성하려면, check가 곧 n인 경우의 예외상황을 만들어줘야한다. 즉 입력값 n이 11이었을 상황을 예외처리)

 

이젠 위치 추적만 남았다.

이 시작값들의 위치는 규칙을 가지고 있다.

1	2	6	7	15
3	5	8	14
4	9	13
10	12
11

i가 짝수일때는 파란 배경값에 위치하며 ==> (1,i),

i가 홀수일때는 회색 배경값에 위치한다 ==> (i,1)

여기서 입력값 n과 check값과의 차이만큼 해당 좌표를 옮겨주면 된다.

그리고 좌표 옮겨주는 것도 i가 짝수냐 홀수냐에 따라 분류할 수 있다.

i가 짝수일때는 옮길때마다 x값은 증가, y값은 감소한다. 즉 (1+diff, i-diff)

i가 홀수일때는 옮길때마다 x값은 감소, y값은 증가한다. 즉 (1-diff, i+diff)

 

1	2	6	7	15
3	5	8	14
4	9	13
10	12
11

아까 예시인 입력값 9의 경우, 11에서 7로 check값도 바꾸고 i값도 이전값인 4로 돌려놨다.

i는 짝수이기 때문에 check값의 좌표는 (1,4).

9와 7의 차잇값은 2기 때문에 짝수 규칙에 따라 (1+2, 4-2)로 (3,2)라는 좌표값을 얻게 된다.

이후 할 일은? 3/2로 저 값을 출력하면 끝.

    int n, check(1), x(0), y(0);
    cin >> n;
    for(int i = 1; ; i++) {
        if(check < n) {
            check += i;
        } else {
            int diff = check-n;
            if(diff != 0) {
                i -= 1;
                check -= i; //이전값에서 비교
                diff = n-check;
            }

            if(i%2 == 0) {  //짝수
                x = 1+diff;
                y = i-diff;
            } else {
                x = i-diff;
                y = 1+diff;

            }
            break;
        }
    }
    cout << x << "/" << y << "\n";