[C] 분수찾기 (백준 알고리즘 1193번)

https://www.acmicpc.net/problem/1193

1193번: 분수찾기

1. 문제

---

💡 문제

무한히 큰 배열에 다음과 같이 분수들이 적혀있다.

1/1	1/2	1/3	1/4	1/5	…
2/1	2/2	2/3	2/4	…	…
3/1	3/2	3/3	…	…	…
4/1	4/2	…	…	…	…
5/1	…	…	…	…	…
…	…	…	…	…	…

이와 같이 나열된 분수들을 1/1 → 1/2 → 2/1 → 3/1 → 2/2 → … 과 같은 지그재그 순서로 차례대로 1번, 2번, 3번, 4번, 5번, … 분수라고 하자.

X가 주어졌을 때, X번째 분수를 구하는 프로그램을 작성하시오.

💡 입력

첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다.

💡 출력

첫째 줄에 분수를 출력한다.

 

 

2. 풀이

---

#include <stdio.h>

int main(){
    long input = 0, num = 1, check = 0, location = 0, a = 1, reverse = 1;
    
    scanf("%ld", &input);
    
    while (num <= input){
        check += 1;
        num += check;
        
        if (reverse == 1) reverse = 0;
        else reverse = 1;
    }
    
    location = input - (num - check);
    
    if (location != 0){
        a += location;
        check -= location;
    }
    
    if (reverse != 0) printf("%ld/%ld\n", a, check);
    else printf("%ld/%ld\n", check, a);
}

 

3. 메모

---

 어우.. 역시 수학은 너무 어렵다.. 이건 수학이 아닌가? 무튼 어렵다.. 문제를 제대로 안 읽고 코딩해서 가볍게 첫 시도는 실패했다. 지그재그로 카운트 할 줄이야 ㅡㅡ..

 

#include <stdio.h>

int main(){
    // 값을 입력받을 input.
    // 1행에 들어갈 값들을 체크하기 위한 num, num은 곧 해당 대각선 줄의 시작 번호이다.
    // 이전 num과 현재 num의 값 차이를 비교하기 위한 check, check은 분모에 들어갈 것이다.
    // 체크할 값이 num과 몇 칸 떨어져 있는지를 체크하기 위한 location
    // 분자로 들어갈 a.
    long input = 0, num = 1, check = 0, location = 0, a = 1;
    
    scanf("%ld", &input);
    
    // num은 대각선 줄의 시작 번호로, 이 num이 input보다 작거나 같다면 계속해서 while문을 반복한다.
    while (num <= input){
    
    	// (1, 1)의 칸 넘버는 1이다. 고로 num은 1부터 시작하며,
        // 1행 기준 칸 넘버는 (지그재그가 아닌 우측 상단에서 좌측 하단으로 내려간다고 가정 '/')
        // 1, 2, 4, 7, ..., 이런 식으로 값이 커져간다.
        // 이에 check += 1을 통해 기존 값 1에 1, 2, 3, ... 을 더해준다.
        check += 1;
        num += check;
    }
    
    // check 값은 우리가 원하는 값이 맞지만, num의 경우 check이 한 번 더 더해졌기 때문에
    // num에서 check를 뺀 값을 다시 input에서 빼줘야
    // 우리가 원하는 1행의 칸 넘버에서 몇 칸 떨어졌는지 알 수 있다.
    location = input - (num - check);
    
    // location이 0이 아니라는 것은 곧 1행이 아니라는 것이기에
    if (location != 0){
    	
        // location 값 만큼 분자는 더해주고 분모는 빼준다.
        a += location;
        check -= location;
    }
    
    printf("%ld/%ld\n", a, check);
}

 

 이 경우는 지그재그가 아닌, '/' 대각선으로 카운트 할 때이다. 그러니 reverse라는 함수를 하나 만들어 1행의 1, 3, 5, ... , 홀수열에서 reverse를 체크해 분자, 분모를 뒤집어서 printf 하도록 하자.

 

#include <stdio.h>

int main(){
    long input = 0, num = 1, check = 0, location = 0, a = 1;
    
    // reverse가 0이라면 분자, 분모를 뒤집을 것이다.
    long reverse = 1;
    
    scanf("%ld", &input);
    
    while (num <= input){
        check += 1;
        num += check;
        
        // while문이 반복될 때마다 reverse 값을 바꿔준다.
        if (reverse == 1) reverse = 0;
        else reverse = 1;
    }
    
    location = input - (num - check);
    
    if (location != 0){
        a += location;
        check -= location;
    }
    
    // reverse가 0이 아니라면 (짝수열이라면), 그대로
    if (reverse != 0) printf("%ld/%ld\n", a, check);
    // 홀수열이라면, check이 분자로 가고 a가 분모로 간다..!
    else printf("%ld/%ld\n", check, a);
}