[백준] 1193번 - 분수찾기

문제 >

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

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)가 주어진다.

 

출력 >

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

 

해결방법 > 

행렬을 각 원소를 대각선 부분집합으로 생각하면 { 1/1 } , { 1/2, 2/1 }, { 3/1, 2/2, 1/3 }, ...이런 방식으로 나열된다.

i 번째 대각선은 a[i] = a[i-1] + 1 번째의 분수를 포함함으로 a[i-1] < x <= a[i]를 만족하는 대각선을 찾고

부분집합의 각 원소가 갖는 규칙을 찾아낸다.

 

c++

#include <iostream>

using namespace std;

int main(){
    int num;
    int sum = 1, size = 1;
    int st;
    int s;
    int i = 2;
    cin >> num;

    if(num == 1){
        cout << "1/1" <<'\n';
        return 0;
    }
    while(1){
        if(num > sum && num <= sum + i){
            st = i;
            s = (sum + i) - num;
            break;
        }
        sum += i;
        i++;
    }
    if(st % 2 == 1){
        cout << s + 1 << '/' << st - s << '\n';
    }else{
        cout << st - s << '/' << s + 1 << '\n';
    }
}

 

java

package baekjoon;

import java.util.*;

public class BOJ_1193 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int x = sc.nextInt();
		String s;
		int a = 1;
		int idx, dif;
		
		for(int i = 1; ;i++) {
			if(x <= a) {
				idx = i;
				dif = a - x;
				break;
			}
			a = a + (i+1);
		}
		if(idx % 2 != 0) {
			s = (dif + 1) + "/" + (idx - dif);
		}
		else
			s = (idx - dif) + "/" + (dif + 1);
		System.out.println(s);
	}
}

 

 

문제링크 >

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

1193번: 분수찾기