백준 1193번 "분수 찾기" 문제

백준 1193번

1193번: 분수찾기

• 문제 설명

정수 X가 주어졌을 때, 대각선 방향으로 놓인 분수들 중에서 X번째 분수를 구하는 프로그램을 작성하세요. 이때, 분수는 왼쪽 아래에서 시작해서 오른쪽 위로 번갈아가며 지그재그 방향으로 놓입니다. 첫 번째 분수는 1/1이고, 두 번째 분수는 1/2 또는 2/1 중 하나입니다. 세 번째 분수는 3/1, 2/2, 또는 1/3 중 하나이며, 네 번째 분수는 1/4, 2/3, 3/2, 또는 4/1 중 하나입니다.

 

• 소스코드

N = int(input())

count = 1 # 대각선

while N > count:
    N -= count
    count += 1

if count % 2 == 0:
    numer = N
    denomi = count - N + 1
else:
    numer =  count - N + 1
    denomi = N

print(f'{numer}/{denomi}')

• 문제 풀이

이 문제는 처음 봤을때 어떻게 푸는지 생각을 하는게 제일 오래걸렸던 문제이다.

 

 분수의 위치를 파악하면 된다. 먼저 분수를 대각선으로 나눌 수 있다. 대각선의 번호는 1부터 시작하여 1씩 증가한다. 각 대각선에는 분자와 분모의 합이 일정한 분수들이 위치한다. 예를 들어, 첫 번째 대각선에는 1/1만 위치하며, 두 번째 대각선에는 1/2와 2/1이 위치한다.

먼저 X번째 분수가 위치한 대각선을 구하고. 이를 위해 count를 1로 초기화하고, while문을 이용하여 N이 count보다 클 때까지 count를 1씩 증가시키면서 N에서 count를 빼준다. 이렇게 하면 count는 N번째 분수가 위치한 대각선의 번호가 된다.

다음으로, 대각선에서 N번째 분수가 위치한 곳을 파악하고. 대각선에서의 위치에 따라 분자와 분모가 결정된다. 대각선 번호가 홀수일 경우, 분자가 작아지고 분모가 커지고. 대각선 번호가 짝수일 경우, 분자가 커지고 분모가 작아진다. 이를 바탕으로 if문을 이용하여 대각선 번호가 짝수일 때와 홀수일 때의 분수를 각각 numer와 denomi 변수에 저장하여.

 f-string을 이용하여 {numer} / {denomi} 형태의 분수를 출력.