[구현/수학] 백준 1193 분수찾기 - Python

 

[ Contents ]

 

 

1. 문제 (링크 참조)

1193번: 분수찾기

 

 

 

2. 문제 풀이

 위와 같은 순서로 배열되는 분수의 규칙을 파악하는 문제입니다. 입력으로는 정수 X가 주어지며, 위와 같은 규칙에 따라 X번째 분수를 출력해야 합니다.

 

 

 

2022.01.19 - [Algorithm] - [Algorithm] 단골 1번 문제, 구현 / 수학

[Algorithm] 단골 1번 문제, 구현 / 수학

 패턴(규칙)을 파악하는 수학문제입니다. 지그재그로 왔다갔다 하므로, 언뜻 보면 상당히 복잡한 패턴입니다.

 

 

 하지만, 대각선으로 보면 조금 쉬워집니다. 대각선의 길이는 1씩 늘어나며, 홀수 대각선은 우상향이고 짝수 대각선은 좌하향 방향으로 진행됩니다.

 이 규칙을 코드로 구현하면 아래와 같습니다.

 

 

 

3. 코드

X = int(input()) #입력

cnt = 0 # count
diagonal = 0 # 대각선 번호
n = 0 # 대각선 중 n번째 수

# X가 속한 대각선 찾기
for i in range(1,X+1):
    cnt += i
    if cnt >= X:
        diagonal = i # i번째 대각선 중
        n = X-(cnt-i) # n번째 수
        break

 먼저 X가 속한 대각선이 몇 번째인지 찾아야 합니다. 대각선의 길이는 1씩 늘어나므로, 1 + 2 + 3 .. 더하며 cnt가 X보다 커지는 때를 구합니다. 

 몇 번째 대각선인지 구하면, 나머지를 통해 대각선의 몇 번째 수인지를 알 수 있습니다.

 

 

# 순서 찾기
numerator = 0 # 분자
denominator = 0 # 분모

# 홀수 대각선일 때 (우상향)
if diagonal % 2 == 1:
    numerator = diagonal + 1
    denominator = 0
    
    for j in range(n):
        numerator -= 1
        denominator += 1

 지그재그로 이동하므로, 홀수/짝수 대각선에 따라 분자/분모가 변하는 규칙이 다릅니다.

 홀수 대각선의 경우, 오른쪽 상단 방향으로 진행하며 분자는 1씩 작아지고, 분모는 1씩 커집니다.

 

 

 

# 짝수 대각선일 때 (좌하향)
elif diagonal % 2 == 0:
    numerator = 0
    denominator = diagonal + 1
    
    for j in range(n):
        denominator -= 1
        numerator += 1

# 출력
print(f'{numerator}/{denominator}')

 짝수 대각선은 왼쪽 상단 방향으로 진행하며 분자는 1씩 커지고, 분모는 1씩 작아집니다.

 이후, f-String을 이용해서 X번째 분수를 출력합니다.

 

 

 

<전체 코드>

X = int(input()) #입력

cnt = 0 # count
diagonal = 0 # 대각선 번호
n = 0 # 대각선 중 n번째 수

# X가 속한 대각선 찾기
for i in range(1,X+1):
    cnt += i
    if cnt >= X:
        diagonal = i # i번째 대각선 중
        n = X-(cnt-i) # n번째 수
        break

        
# 순서 찾기
numerator = 0 # 분자
denominator = 0 # 분모

# 홀수 대각선일 때 (우상향)
if diagonal % 2 == 1:
    numerator = diagonal + 1
    denominator = 0
    
    for j in range(n):
        numerator -= 1
        denominator += 1

# 짝수 대각선일 때 (좌하향)
elif diagonal % 2 == 0:
    numerator = 0
    denominator = diagonal + 1
    
    for j in range(n):
        denominator -= 1
        numerator += 1

# 출력
print(f'{numerator}/{denominator}')