🐷전동준(Jeon DongJun)

Go with the flow

[BOJ/백준-Python]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)가 주어진다.

출력

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

예제 입력 1

예제 출력 1

1/1

예제 입력 2

예제 출력 2

1/2

예제 입력 3

예제 출력 3

2/1

예제 입력 4

예제 출력 4

3/1

예제 입력 5

예제 출력 5

2/2

예제 입력 6

예제 출력 6

1/3

예제 입력 7

예제 출력 7

1/4

예제 입력 8

예제 출력 8

2/3

예제 입력 9

예제 출력 9

3/2

예제 입력 10

예제 출력 10

2/4

해결할 방법을 생각해보자.💡

대각선이 이동하며 지그재그 형식으로 이동하고있다.

이걸 보면 규칙을 찾을 수 있다. 대각선을 기준으로 생각해보면, 1번째 대각선에서는 1개의 분수, 2번째 대각선에서는 2개의 분수, 3번째 대각선에서는 3개의 분수.. 즉, n번째 대각선에서는 n개의 분수가 존재한다는 것을 확인할 수 있다. 그리고 홀수 대각선에서는 n/1에서 1/n으로 가는 것을 확인할 수 있다. 즉, 홀수 대각선에서는 칸이 이동할 때 분자가 1씩 줄어들고 분모가 1씩 늘어나는 것을 알 수 있다. 그렇다면 짝수 대각선에서는 1/n -> n/1 이런 형식일 것이다. 이 규칙을 숙지해 코드를 짜보자!

숫자 X를 받아주자.

X = int(input())

그리고 받은 숫자 X와 같은 숫자 변수를 하나 만들어놓자.(이유는 추후에 나온다.)

num = X

이제 line이라는 변수를 선언해줄 것이다. line은 n번째 대각선을 나타내는 변수다. 이 문제에서는 입력값이 최소 1부터 시작하기 때문에 무조건 1번째 대각선부터 시작한다. 그래서 line 에 1를 저장하여 시작해준다.

line = 1

이제 입력받은 숫자 X가 위치한 대각선을 구하기 위한 식을 짜보자. 대각선 규칙은 이렇다.

1 : 1번 대각선

2, 3 : 2번 대각선

4,5,6 : 3번 대각선

7,8,9,10 : 4번 대각선

2292번 벌집 문제처럼 while문을 사용하면 수월하다.

while num > 1:
    line += 1
    num -= line

위 대각선 규칙을 보면 한 대각선에 가지고 있는 값이 1씩 증가한다. 즉 1, 2/3, 4/5/6, 7/8/9/10, 11/12/13/14/15 이라는 뜻.

따라서 대각선 변수인 line이 1씩 추가되며, 그 만큼 num의 숫자가 깎이면서 해당 숫자가 몇번째 대각선에 위치한지 확인할 수 있다.

예를 들어, 10이면 line이 4로, 네 번째 대각선에 위치한다는 것을 알 수 있다.

대각선의 위치를 구했다면, 해당 대각선에서 몇 번째 칸에 위치하는지를 구해보자.

위에서 확인했듯이 대각선이 이동할때마다 갖고있는 값들의 크기가 1씩 증가하는 것을 확인할 수 있다. 이제 원래 입력받은 값 X를 활용할 차례가 온 것 이다.

우선 합계를 나타내는 sum 변수를 선언

sum = 0

이제 반복문을 실행할 것인데 범위는 1부터 line까지다. 이러면 현재 값이 위치한 대각선의 전 대각선까지만 범위가 잡힌다. 예를들어 입력받은 X가 10일때 아까 위에서 보았듯이 10은 네 번째 대각선에 위치해 있다. range(1, line)으로 범위를 잡으면, 세번째 대각선 까지의 값들의 개수가 잡히는 것이다.

각 대각선이 가지고 있는 값들의 개수를 sum에 더해준다고 생각하면 된다.

for i in range(1, line):
    sum += i

그리고 몇 번째 칸을 뜻하는 sequence라는 변수를 선언해준다. 입력받은 값 X에서 sum을 빼주면된다. 입력받은 값이 10이라면, 10 - 6으로 4가 되어 네 번째 대각선에 위치해 있으며 4번째 순서에 있다는 것을 알 수 있다.

sequence = X - sum

이제 맨 처음에 봤던 규칙들을 상기해보자. 홀수 대각선에서는 n/1에서 1/n으로 가는 것을 확인. 짝수 대각선에서는 1/n에서 n/1로 가는 것을 확인했다.

홀수 : 대각선 내에서 칸 이동 시 분자가 줄어들고 분모가 커짐

짝수 : 대각선 내에서 칸 이동 시 분자가 커지고 분모가 줄어들음

이걸 코드로 표현해보자. 여기서 son은 분자, mom은 분모를 뜻한다.

# 홀수 대각선
if line % 2 != 0:
    son = line
    mom = 1
    print(f'{son - sequence + 1}/{mom + sequence - 1}')
# 짝수 대각선
else:
    son = 1
    mom = line
    print(f'{son + sequence - 1}/{mom - sequence + 1}')

코드💻

X = int(input())
num = X
line = 1

while num > 1:
    line += 1
    num -= line

sum = 0
for i in range(1, line):
    sum += i
sequence = X - sum


if line % 2 != 0:
    son = line
    mom = 1
    print(f'{son - sequence + 1}/{mom + sequence - 1}')
else:
    son = 1
    mom = line
    print(f'{son + sequence - 1}/{mom - sequence + 1}')

해결 로그

문제 푼 날짜	체크
2022-06-02	✔

2022 196
2021 22

맨 위로 이동 ↑

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	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	…	…	…	…	…
…	…	…	…	…	…