백준 알고리즘 | 1193 : 분수찾기 (Python / 파이썬)

---

분수찾기 성공분류

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
0.5 초 (추가 시간 없음)	256 MB	33368	17043	15184	53.300%

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

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

​

출력

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

​

알고리즘 분류

수학

구현

---

 

백준 알고리즘 # 1193번 : 분수찾기

출처:  https://it-coco.tistory.com/entry/%EC%B6%9C%EB%A0%A5-print-sep-end

x = int(input())        # x = 14
line = 1

while x > line:
    x -= line           # x = 14, 13, 11, 8, 4
    line += 1           # line = 1, 2, 3, 4, 5

if line % 2 == 0:       
    a = x               
    b = line - x + 1
else:
    a = line - x + 1
    b = x

print(a, "/", b, sep = "")

풀이

표를 보면 규칙성은 [1/1], [1/2, 2/1], [3/1, 2/2, 1/3], [1/4, 2/3, 3/3, 4/1] ... 처럼 단순해보이지만

이것을 코드풀이로 옮기기는 힘들었다..

​

마지막에 작성한 print() 코드부터 훑어보면

a와 b를 /로 나눠서 a는 왼쪽, b는 오른쪽으로 봐서

a = [1], [1, 2], [3, 2, 1], [1, 2, 3, 4] ...

b = [1], [2, 1], [1, 2, 3], [4, 3, 2, 1] ...

위와 같은 규칙이 있다는 것을 알 수 있었다.

​

다시 처음으로 돌아와서 변수 x를 설정해서 정수를 입력받고

변수 line은 각각의 대각선에 해당한다고 생각하면 된다.

​

다음으로 while문을 사용해서 변수 x로 주어진 14의 위치를 찾기위해서 while문을 반복해서

변수x가 대각선 line 수보다 작아질 때, 해당하는 대각선에 찾고있는 변수 x가 있는 것이므로 while문을 탈출한다.

x = 14, 13, 11, 8 , 4

line = 1, 2, 3, 4, 5

위와 같이 x = 4, line = 5, x번째 분수가 있는 line의 위치를 알게 되었다.

​

마지막으로 if문을 사용해서 만약 line이 짝수라면 (line % 2 == 0)

a = [1, 2], [1, 2, 3, 4] ...

b = [2, 1], [4, 3, 2, 1] ...

위 결과를 찾을 수 있게끔 코드를 짜면 되지만

​

주어진 예제 입력은 line이 5인 홀수이므로 else문으로 가서

a = [1], [3, 2, 1] ...

b = [1], [1, 2, 3] ...

위 결과가 나오게끔 코드를 짜고

a = 5 - 4 + 1 = 2

b = 4

위의 a, b 변수를 sep = ""로 붙여서 출력해주면 끄---읏!👏

​

자세한 코드가 궁금하신 분들은 아래 GitHub 참고해주세요🙏

wook2124/Algorithm

최종 소스코드