[백준/Python] 1193번: 분수찾기 풀이

출처: https://www.acmicpc.net/problem/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)가 주어진다.

 

출력

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

---

풀이 전략

시간제한이 있기 때문에 나이브하게 풀 수 없다. 규칙을 찾아서 바로 계산하도록 만들어야 한다.

 

여기에서 같은 배경색끼리는 (분모+분자) 값이 같다. 편의상 분모를 x, 분자를 y라고 하면 x+y 값은 대각선 방향으로 일정하게 유지된다. 같은 x+y 값을 갖는 칸의 수는 1(연노랑), 2(연빨강), 3(연초록), 4(연파랑), 5(연보라), ... 이렇게 1씩 증가한다. 학교에서 어느 학생을 찾을 때 1) 학생의 반을 먼저 구한 뒤, 2) 해당 반에서 몇 번째 학생인지 구하는 방식으로 풀었다.

 

문제를 풀기 위해 계산해야 하는 것은 다음의 두 가지로 결정된다.

1) 찾으려는 n이 몇 번째 대각선에 해당하는지

2) 찾으려는 n이 같은 대각선 내에 몇 번째 칸인지

 

예를 들어, 14번째 칸을 찾의 경우

1) 5번째 대각선에 있고

2) 해당 대각선 내 11~15 중 4번째 칸이다.

---

1) n이 몇 번째 대각선에 해당하는지 구하기

for문을 통해 1+2+3+...을 더하면서 n보다 커지면 멈춘다. 

i=0
cnt=0
while cnt<n:
    i+=1
    cnt+=i

14번째 칸은 5번째 대각선의 4번째 칸이다. 위의 부분을 실행하면 i==5, cnt==15가 되는데 이때 i는 1)을, cnt는 해당 대각선의 마지막 번호를 의미한다.

 

2) n이 대각선 내에서 몇 번째 칸인지 구하기

홀수번째 대각선은 왼쪽 아래에서부터 y가 1씩 증가하고 x가 1씩 감소한다. 반면 짝수번째 대각선은 오른쪽 위에서부터 x가 1씩 증가하고 y가 1씩 감소한다.

 

14번째 칸이 속한 연보라색 대각선을 보면, 칸 번호가 1씩 감소할 때마다 x가 1씩 증가한다.

따라서 x == 1 + (마지막 칸과 현재 칸의 차이) == 1 + cnt - n

y는 (x+y) - x인데 x+y==(i+1)로 일정하므로, y == (i+1) - (1 + cnt - n) == i - (cnt - n)

 

그런데 위의 식은 홀수 번째 대각선에만 해당되며 짝수 번째에는 x, y가 뒤바뀐다. 이는 다음의 코드로 표현할 수 있다.

if i%2==1: #홀수
    x = 1 + cnt - n
    y = i - (cnt - n)
else: #짝수
    y = 1 + cnt - n
    x = i - (cnt - n)

 

이를 한 줄로 줄이면 아래와 같다.(참고: www.acmicpc.net/source/27657152)

(1+cnt-n,i-(cnt-n))[::i%2*2-1]

위의 코드는 tuple (1+cnt-n, i-(cnt-n))을 양의 순서로 놓을지 음의 순서로 놓을지 정하는 것이다. i가 홀수인 경우 i%2*2-1==1이 되므로 홀수 대각선일 때의 x, y 순서가 된다. i가 짝수인 경우 i%2*2-1==-1이 되므로 짝수 대각선 일 때의 x, y 순서가 된다.

 

[::i%2*2-1]이 뭔지 모르겠다면? ― [관련 링크] 2021.05.13 - [TIP/Python] - [파이썬 TIP] Extended Slices

---

코드