[알고리즘 문제풀이] 분수찾기

문제 출처: https://www.acmicpc.net/problem/1193

              (Baekjoon Online Judge)

문제

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

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

출력

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

예제 입력: 14

예제 출력: 2/4

내가 작성한 코드

실행결과

이번 문제 또한 계차수열을 이용해서 풀었습니다. 매트릭스 안의 분수로는 규칙이 잘 보이지 않아서 분수를 일렬로 놓고 규칙을 찾으려고 했습니다.

1/1 || 1/2, 2/1 || 3/1, 2/2, 1/3 || 1/4, 2/3, 3/2, 4/1 || 5/1, 4/2, 3/3, 2/4, 1/5 || .......

"||"을 기준으로 규칙이 보이시나요? "||"을 기준으로 순차적으로 1그룹, 2그룹... 이라고 했을때 홀수그룹은 분자가 그룹의 숫자로 시작하고 분모는 그룹의숫자 - 분자 + 1으로 시작하죠, 짝수그룹의 경우는 그 반대구요.

그래서 저는 계차수열(코드의 For문)을 통해 그룹을 먼저 구했고, 그룹의 짝홀수 여부(if else문)에 따라 각각 분모(down), 분자(up)를 구했습니다.

규칙찾기 문제에서는 계차수열을 이용한 문제들이 많은 것 같네요.