[파이썬 풀이] 백준 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 = int(input())

if X == 1 :
    print("1/1")
else:
    last = 3
    plus = 2
    while X > last :
        plus+=1
        last+=plus
    m = last-X
    if plus%2 == 0 :
        print(f"{plus-m}/{1+m}")
    else:
        print(f"{1+m}/{plus-m}")

 

코드 설명   

각각의 분수들이 순서대로 배정 받는 수는 아래와 같습니다.

위 그림을 토대로 표의 규칙을 나열하자면,

---

1. 묶인 분수들은 분모와 분자를 더한 수가 같다.

 

2. 분수들을 묶음별로 보았을때, 각각의 묶음에서 배정받은 수 중 가장 큰 수는

위 그림과 같은 규칙을 따라 증가합니다.

 

3. (해당 묶음의 가장 큰 수)와 (직전 묶음의 가장 큰 수)의 차이를 plus이라 할 때,

plus가 만약 짝수면, (해당 묶음의 가장 큰 수)는 그 묶음의 첫번째 열에 위치한 수가 되고,

plus가 만약 홀수라면, (해당 묶음의 가장 큰 수)는 그 묶음의 첫번째 행에 위치한 수가 됩니다.

 

4.(해당 묶음의 가장 큰 수 - 입력 받은 수)를 m이라 할 때,

plus가 짝수일 때, N의 분수는 plus-m/1+m이 되고,

plus가 홀수일 때,  N의 분수는 1+m/plus-m이 됩니다.

 

---

이 됩니다.

 

위에있는 규칙을 활용하여 코드를 구성했습니다.

 

if X == 1 :
    print("1/1")

만약 X가 1일땐 답이 무조건 1/1이므로, 불필요한 과정을 줄이기 위해 바로 1/1을 출력해줍니다.

 

else:
    last = 3
    plus = 2
    while X > last :
        plus+=1
        last+=plus

X가 1이 아닐때 반복문을 실행합니다.

일단 반복문 내에서 사용될 변수들을 반복문 밖에 선언해줍니다.

현재 묶음의 가장 큰 수가 담길 변수 last와 묶음이 넘어갈 때 마다 last를 증가시켜줄 변수 plus를 선언해줍니다.

그 뒤 반복문을 사용해서 X가 last보다 크다면 plus값을 1 증가 시키고, last에 plus를 더해줍니다.

 

    m = last-X
    if plus%2 == 0 :
        print(f"{plus-m}/{1+m}")
    else:
        print(f"{1+m}/{plus-m}")

입력한 수와 현재 묶음의 차이 값을 저장하는 변수 m을 선언해줍니다.

만약 plus가 짝수라면, plus-m/1+m을 출력하고,

plus가 홀수라면, 1+m/plus-m을 출력해 줍니다.

 

 

관련 개념 정리   

input

파이썬에서는 값을 사용자로부터 입력받을때 input함수를 사용합니다.

입력받은 값을 넣을 변수 이름 = input("띄울 메세지")

 

단! input함수는 입력받은 모든 내용을 문자열로 인식합니다. 따라서 입력받은 내용을 정수로 변환하려면

d = int(input())

와 같은 형태로 작성하거나,  나중에 변수를 사용할때

print(int(d)+2)

와 같이 int()로 감싸서 작성할 수 있습니다.

 

 

if문

<조건> 하면, <코드>를 실행하고 싶을때 쓸 수 있는것이 바로 if문입니다.

기본적인 형태는 아래와 같습니다.

if 조건문 1:
	실행 코드 1 ...
elif 조건문 2:
	실행 코드 2 ...
else:
	실행 코드 3 ...

해석을 하자면, 조건문 1을 충족하면 실행 코드 1을 실행하고, 그게 아닌 조건문 2를 충족하면 실행 코드 2를 실행한다.

조건문 1과 조건문 2를 모두 충족하지 않으면 실행 코드 3을 실행한다. 입니다.

elif와 else는 필수는 아닙니다.

 

 

while문

while문은 for문과 같은 반복문입니다.

while 조건 :
	실행할 코드

기본 구조는 위와 같고, 조건이 충족할때만 코드를 실행합니다.

whlile문 내에 break를 입력하면 whlie문을 빠져 나올 수 있고,

continue를 입력하면 while문의 처음으로 돌아갑니다.

 

 

산술 연산자

x+y	x 더하기 y
x-y	x 빼기 y
x*y	x 곱하기 y
x/y	x 나누기 y
x//y	x 나누기 y의 몫
x%y	x 나누기 y의 나머지
x**y	x의 y제곱

 

 

f-string

f-string은 문자열 포매팅 방식 중 하나로, js의 백틱과 비슷한 기능을 제공합니다.

a=10
print(f"I have {a} apples")
# I have 10 apples

위와 같이 쉽게 문자열 사이에 변수값을 넣어 반환해줍니다.