1193번(분수 찾기) 파이썬(Python) 풀이 공유

들어가며

여러 방면을 고려해야 하는 문제라 그런지 약간 복잡하게 느껴지는 문제였다. 다른 분들이 올려놓은 코드와 비교해보았을 때 방향성은 비슷했으나, 구현 방식에는 약간의 차이가 있다.

---

1. 문제

• 1193번 분수 찾기

시간 제한	메모리 제한
0.5초 (추가 시간 없음)	256 MB

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

col1	col2	col3	col4	col5
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번째 분수를 구하는 프로그램을 작성하시오.

1.1. 입력

첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다.

1.2. 출력

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

1.3. 예제

입력	출력
1	1/1
2	1/2
3	2/1
4	3/1
5	2/2
6	1/3
7	1/4
8	2/3
9	3/2
14	2/4

---

2. 풀이

문제를 보면, 표의 분수는 아래와 같이 지그재그로 순번이 매겨진다.

이를 아래 표와 같이 화살표 방향에 따라 생성되는 단계별로 나누었는데, 이 과정에서 몇 가지 규칙을 발견하였다.

단계	순서 범위	분수	최대값	개수	정렬방식
1단계	1	1/1	1	1개	해당없음
2단계	2 ~ 3	1/2, 2/1	2	2개	오름차순
3단계	4 ~ 6	3/1, 2/2, 1/3	3	3개	내림차순
4단계	7 ~ 10	1/4, 2/3, 3/2, 4/1	4	4개	오름차순
5단계	11 ~ 15	5/1, 4/2, 3/3, 2/4, 1/5	5	5개	내림차순

• 단계, 분수의 개수, 최댓값의 수는 전부 같다.
• 단계가 홀수인 경우 정렬 방식은 내림차순이고, 짝수인 경우 오름차순이다.
• 단계를 step이라고 할때, 순서 범위는 1 + step으로 증가하는 범위를 나타낸다.

X = int(input())

step = 1
term = step + 1
start = 0
end = 1

while X > end:
    step += 1
    start = end
    end += term
    term += 1

if step % 2:
    print(f"{end+1 - X}/{X - start}")

else:
    print(f"{X - start}/{end+1 - X}")

• Line 1 : 변수 X를 찾고자 하는 분수의 순서로 초기화한다.
• Line 3 : 단계를 변수 step에 1로 초기화한다.
• Line 4 : 순서 범위의 증가 계수는 step + 1로, term에 초기화한다.
• Line 5 - 6 : 1단계의 분수는 1/1이므로, 시작 값을 나타내는 변수 start은 0, 종료 값을 나타내는 변수 end는 1로 초기화합니다. 이때, end는 특정 단계에 존재하는 분수를 구성하는 최댓값이다.
• Line 8 - 12 : X가 최댓값보다 작을 때에만 반복을 수행하며, 각 반복을 수행할 때 step를 1 증가, start를 이전 종료값(최댓값)으로 초기화, end는 term만큼 증가, term은 1 증가시킨다.
• Line 14 - 15 : step이 홀수인 경우 분자는 end에 X 값을 뺀 후 1을 더한 값을, 분모는 X에 start 값을 뺀 값으로 출력한다.
• Line 17 - 18 : step이 짝수인 경우 분자는 X 값에서 start를 뺀 값을, 분모는 end에 X 값을 뺀 후 1을 더한 값으로 출력한다.

---

마치며

처음 작성하고 제출한 코드는 스스로 봐도 정말 가독성이 매우 떨어지는 코드라고 생각한다.

X = int(input())

top = 1
bottom = 1

if X > 1:
    count = 2
    end = 2

    while X > count:
        count += end
        end += 1

    if X < count:
        end -= 1
        count -= end

    if end % 2:
        top = end - (X - count)
        bottom = [number for number in range(
            count, count + end)].index(X) + 1
    else:
        top = [number for number in range(
            count, count + end)].index(X) + 1
        bottom = end - (X - count)

print(f"{x}/{y}")

제출하고 정답인 사실을 확인하고 나서 한결 마음이 편안해졌는지, 블로그 작성을 위해 여유롭게 코드를 재구성할 수 있었다. 지금봐도 위의 변수명이 각각 무엇을 의미하는지 감이 잘 안 잡히는데, 변수 네이밍의 중요성을 다시 한 번 느낀다.