백준 1193번 [파이썬 알고리즘] : 분수찾기

 

[Python] 백준 알고리즘 온라인 저지 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	…	…	…	…	…
…	…	…	…	…	…

Python3 코드

input_num = int(input())

line = 0  # 사선 라인
max_num = 0  # 입력된 숫자(input_num 변수)의 라인에서 가장 큰 숫자
while input_num > max_num:
    line += 1  
    max_num += line  

gap = max_num - input_num 
if line % 2 == 0:  # 사선 라인이 짝수번째 일 때
    top = line - gap  #분자
    under = gap + 1  #분모
else :  # 사선 라인이 홀수번째 일 때
    top = gap + 1  #분자
    under = line - gap  #분모
print(f'{top}/{under}')

 

 

Python3 코드 풀이

 

1. 코드의 전체적인 풀이

이번 문제는 사선을 따라서 지그재그로 정수가 배열되고 이 정수에 따라 분수가 매칭 될 때, 정수 x가 주어지면 그에 대응하는 분수를 출력하는 문제이다. 코드를 작성할 때에는 사선 라인이 짝수번째인지 홀수번째인지에 따라 입력받는 수에 대응하는 분수를 찾는 규칙이 달라지는 점을 이용해서 문제를 풀었다.

 

2. while 반복문으로 입력받은 정수가 몇 번째 사선 라인에 있는지 확인한다.

input_num = int(input())

line = 0  # 사선 라인
max_num = 0  # 입력된 숫자(input_num 변수)의 라인에서 가장 큰 숫자
while input_num > max_num:
    line += 1  
    max_num += line  

먼저 while 문을 반복하기 전에 line과 max_num이라는 변수에 각각 0을 선언했다. line은 입력받은 정수가 몇 번째 라인에 있는지를 알아내는 데 사용하고 max_num은 입력받은 정수가 있는 사선 라인에 위치한 정수 중 가장 큰 정수를 찾는데 이용된다.

 

입력받은 정수는 input_num이라는 변수에 선언하였고 while 문을 반복하면서 점점 커지는 max_num 이 input_num보다 커지면 반복문을 중단하도록 하였다. 즉, 입력받은 정수가 위치한 사선 라인이 몇 번째인지와 해당 사선 라인에서 제일 큰 수를 알아내는 순간 반복문이 종료된다. 

 

3. 사선 라인이 짝수인지 홀수인지에 따라 분수가 찾는 규칙이 달라진다.

gap = max_num - input_num 
if line % 2 == 0:  # 사선 라인이 짝수번째 일 때
    top = line - gap  #분자
    under = gap + 1  #분모
else :  # 사선 라인이 홀수번째 일 때
    top = gap + 1  #분자
    under = line - gap  #분모

 

1부터 입력 받는 수까지의 정수는 사선 라인을 따라서 지그재그로 배열된다. 사선 라인이 짝수번째이면 오른쪽 끝에서 왼쪽 아래 사선 방향으로 숫자가 커지고, 사선 라인이 홀수번째이면 왼쪽 끝에서부터 오른쪽 위 사선 방향으로 숫자가 커진다.

 

위와 같은 정수의 배열을 이용해서 분수의 분자와 분모를 구하는 식을 작성하였다. 우선 해당 사선 라인에서 제일 큰 수에서 입력받은 수를 빼는 방법으로 gap이라는 변수를 구했다. 그리고 이 gap변수에 1을 더한 값과 line 변수에서 gap 변수를 뺀 값을 이용해서 분수의 분자와 분모를 구할 수 있다.

 

사선 라인이 짝수일 때와 홀수 일 때에 이 분자와 분모에 해당하는 식을 반대로 대입해주어서 문제를 풀 수 있었다. 

 

4. f-string 을 이용해서 출력문을 작성하였다.

print(f'{top}/{under}')

출력 값은 가운데 슬래시 기호(/)를 문자열로 두고 분자와 분모의 값에 변수를 입력해야 한다. 이렇듯 문자열과 변수를 같이 나타내기 위해 편리하게 사용할 수 있는 f-string 포매팅으로 문자열을 작성하였다. 혹시라도 f-string의 사용 예시가 필요하신 분을 위해 이전에 작성한 포스팅 링크를 걸어둔다. ▶파이썬 f-string 사용 예시