문제
무한히 큰 배열에 다음과 같이 분수들이 적혀있다.
이와 같이 나열된 분수들을 1/1 → 1/2 → 2/1 → 3/1 → 2/2 → … 과 같은 지그재그 순서로 차례대로 1번, 2번, 3번, 4번, 5번, … 분수라고 하자.
X가 주어졌을 때, X번째 분수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다.
출력
첫째 줄에 분수를 출력한다.
예제
나의 풀이
n = int(input())
a = 1
b = 1
down = True
for _ in range(n-1):
if a == 1 and b%2 == 1:
b += 1
down = True
elif a%2 == 0 and b == 1:
a += 1
down = False
elif down:
a += 1
b -= 1
elif not down:
a -= 1
b += 1
print(f"{a}/{b}")
- 지그재그 이동 규칙을 네 가지 경우로 나눴다.
- 답은 나오는데 시간 초과에 걸려서 실패했다.
다른 사람의 풀이
n = int(input())
line = 1
while n > line:
n -= line
line += 1
if line%2 == 0:
print(f"{n}/{line-n+1}")
else:
print(f"{line-n+1}/{n}")
- 배열을 대각선으로 나눠보면 한 줄에 n개의 요소가 포함된다. `n-line`을 반복해서 입력값이 몇 번째 줄에 위치하는지를 구한다.
- `line`이 짝수인 경우에는 밑으로 내려가면서 값이 커지고, 홀수인 경우에는 위로 올라가면서 값이 작아지는 점을 이용해서 각각 다른 방법으로 계산한다.
- `line`의 `n`번째에 위치하는 값을 조정해서 출력한다.