[백준] 1193번: 분수 찾기

문제

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

이와 같이 나열된 분수들을 1/1 → 1/2 → 2/1 → 3/1 → 2/2 → … 과 같은 지그재그 순서로 차례대로 1번, 2번, 3번, 4번, 5번, … 분수라고 하자.

X가 주어졌을 때, X번째 분수를 구하는 프로그램을 작성하시오.

풀이

진행 순서이다.

[1,1 시작]
0 오른쪽
1 아래대각선 아래
2 위대각선 위대각선 오른쪽
3 아래대각선 아래대각선 아래대각선 아래
4 위대각선 위대각선 위대각선 위대각선 오른쪽
...

규칙성을 발견할 수 있다.
왼쪽에 있는 숫자는 대각선 이동 횟수이다.
아래대각선으로 이동했을 때는 맨 마지막에 아래로 이동하고
위대각선으로 이동했을때는 맨 마지막에 오른쪽으로 이동한다.

N = int(input())

def solution(N):
    answer = [1, 1]
    dia_max_count = 0
    direction = True  # 아래 대각선
    count = 1
    if count == N:
        return f'{answer[0]}/{answer[1]}'
    while True:
        for i in range(dia_max_count):
            if direction:  # 위 대각선
                answer[0] -= 1
                answer[1] += 1
            else: # 아래 대각선
                answer[0] += 1
                answer[1] -= 1
            count += 1
            if count == N:
                return f'{answer[0]}/{answer[1]}'

        dia_max_count += 1

        if direction: # 위대각선 방향이었을 경우 오른쪽
            answer[1] += 1
        else: # 아래 대각선 방향일 경우 아래
            answer[0] += 1

        direction = not direction
        count += 1
        if count == N:
            return f'{answer[0]}/{answer[1]}'


print(solution(N))