백준 1193번 (T)

백준 온라인 저지 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개 2개 3개 ... 식으로 늘어 간다.
• 각 단계의 합은, 단계 + 1이었다. 1단계는 2, 2단계는 3 이런 식으로.
• 그리고 지그재그라고 써 있는 부분은, 홀수 줄(홀수 단계)은 왼쪽부터, 짝수 줄은 오른쪽부터 본단 얘기다.
• 주어진 n보다 큰 삼각형 수를 찾은 다음에, 빼가면서 값을 찾으면 된다고 생각이 들었다.

n = int(input())

def triangle(n):
    if n == 1:
        return 1
    
    return n + triangle(n-1)

level = 1
while triangle(level) < n:
    level += 1

pile = triangle(level)
x = 0
y = 0

if level % 2 == 0:
    x = level
    y = 1
    while pile > n:
        x -= 1
        y += 1
        pile -= 1
else:
    x = 1
    y = level
    while pile > n:
        x += 1
        y -= 1
        pile -= 1

print("%d/%d" % (x, y))

• 결과는? 런타임 에러. 재귀 에러가 났다. 최대 재귀 깊이를 초과한 모양.

---

아니 이정도도 감당을 못해?

• 그다지 어렵게 구성된 재귀 함수도 아니었는데, 괜히 멋들어지게 쓰려다가 피 봤다.
• 그래서 triangle 함수를 재정의 해줬다. 재귀 안하도록^^

n = int(input())

def triangle(n):
    pile = 0
    for i in range(1, n+1):
        pile += i
    
    return pile

level = 1
while triangle(level) < n:
    level += 1

pile = triangle(level)
x = 0
y = 0

if level % 2 == 0:
    x = level
    y = 1
    while pile > n:
        x -= 1
        y += 1
        pile -= 1
else:
    x = 1
    y = level
    while pile > n:
        x += 1
        y -= 1
        pile -= 1

print("%d/%d" % (x, y))

• 여기서 시간 초과가 떴다.

---

지난한 코드 다이어트의 시작

• 이게 시간 초과가 뜰 만큼 복잡도가 높은가? 라고 생각해서 제한시간을 보니, 0.5초. 화딱지가 났다.
• 단순 산술적 계산을 하는 부분을 최대한 줄이기 시작했다.
• 먼저 pile에서 매번 빼지 않기 위해 diff 변수를 새로 정해 사용해 코드를 수정했다. 시간 초과.
• 다음으로 x와 y값을 하나씩 계산해주는 것을 피하고자, diff를 깡으로 사용해서 계산했다. 시간 초과.
• 보통 이렇게 안 되면 빡치기 시작하는데..

---

읍참함수

• 결국 줄일 수 있는 부분은, triangle 함수밖에 남지 않았다. 바로 꺼내 쓸 수 있게 바꿔줬다.

n = int(input())

triangle = [0]
level = 1
while triangle[-1] < n:
    triangle.append(triangle[-1] + level)
    level += 1

diff = triangle[-1] - n

if level % 2 == 0:
    x = 1 + diff
    y = (level - 1) - diff
    print("%d/%d" % (x, y))
else:
    x = (level - 1) - diff
    y = 1 + diff
    print("%d/%d" % (x, y))

• 덤으로 위쪽에서 헷갈렸던 x와 y값도 손질해 줬다. 전자가 분자, 후자가 분모니까.
• 이렇게 해서 겨우겨우 통과. 아무튼 자력으로 풀긴 했다.