[Baekjoon Online Judge] 백준 1193번 분수찾기(C++, Python)

© 2020 All Rights Reserved. 주식회사 스타트링크

[Baekjoon Online Judge] 백준 1193번 분수찾기

(C++, Python)

(글쓴날 : 2020.04.19)

 

---

* Baekjoon Online Judge, 백준 1193번 문제 C++, Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

백준 1193번 분수찾기

---

1) 문제

문제 링크 : https://www.acmicpc.net/problem/1193

1193번: 분수찾기

---

2) 풀이 과정

* 시간 복잡도 : O(n)

 

임의의 순서가 정해진 배열에 규칙을 가진 분수들이 적혀 있을 때, 주어지는 번호 X에 해당하는 분수를 구하는 문제입니다.

 

저의 경우, C++과 Python을 사용했으며, 규칙은 1/1이 꼭대기가 되도록 배열을 시계방향으로 회전시켜 찾아냈습니다. (전 모니터 돌렸습니다...)

회전시킨 배열에서 각 층별로 분모 혹은 분자의 최댓값과 X의 위치를 구해, 순서를 매기는 방향에 따라 분모와 분자를 1씩 가감하여 문제를 해결했습니다.

---

3) 코드

 

* C++ 코드

#include <iostream>
 
using namespace std;
 
int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int X = 0;
    cin >> X;
 
    int temp = 0;
    int diff = 0;
    int i = 1;
 
    while (X > temp)
    {
        temp += i;
        i++;
    }
 
    i--;
    diff = temp - X;
 
    if (!(i % 2))
        cout << i - diff << "/" << 1 + diff;
    else
        cout << 1 + diff << "/" << i - diff;
 
    return 0;
}

---

* Python 코드

import sys
input = sys.stdin.readline
 
X = int(input())
 
temp = 0
i = 1
 
while X > temp:
    temp += i
    i += 1
 
i -= 1
diff = temp - X
 
if not i % 2:
    print(f"{i - diff}/{1 + diff}")
else:
    print(f"{1 + diff}/{i - diff}")

---