[Python] 백준 알고리즘 1193번 : 분수 찾기

https://www.acmicpc.net/problem/1193

1193번: 분수찾기

 

 

 

 

 

 

👩‍💻문제 이해

그림처럼 지그재그 형태로 진행된다.

전체적인 패턴에서 규칙을 찾으려니 시간이 많이 걸렸다.

하지만 라인을 나눠서 생각해볼때

 

1라인 : 1/1(1개)
2라인 : 1/2 -> 2/1 (2개, 분자 +1, 분모 -1)
3라인 : 3/1 -> 2/2 -> 1/3 (3개, 분자 -1, 분모 +1)
4라인 : 1/4 -> 2/3 -> 3/2 -> 4/1 (4개 , 분자 +1, 분모 -1)
5라인 : 5/1 -> 4/2 -> 3/3 -> 2/4 -> 1/5 (5개, 분자 -1, 분모 +1)

...

다음과 같은 규칙을 가지고 있다.

즉, 

짝수 라인 ->  시작점에서 끝점으로 갈수록 분자 +1, 분모 -1

홀수 라인 ->  시작점에서 끝점으로 갈수록 분자 -1, 분모 +1

 

따라서 구하고자 하는 함수가

1. 몇번 째 라인에 존재하는지

2. 라인안에서 몇번째 순서에 존재하는지

를 구하면 된다.

 

 

 

👩‍💻몇 번째 라인인지와 라인의 마지막 분수 인덱스 사용 : 성공🌈

n = int(input())

line = 0
end = 0
while n > end:
    line += 1
    end += line

diff = end - n
if line%2 == 0:
    top = line - diff
    bottom = diff + 1
else:
    top = diff + 1
    bottom = line - diff

print(top,'/',bottom, sep='')

 

 

n = int(input())

line = 0
end = 0
while n > end:
    line += 1
    end += line
    
# line : 몇 번째 라인
# end : 해당 라인의 마지막 인덱스

 

예시 

 

 

diff = end - n
if line%2 == 0: 
    top = line - diff
    bottom = diff + 1
# 짝수 라인일 때 
else:
    top = diff + 1
    bottom = line - diff
# 홀수 라인일 때
print(top,'/',bottom, sep='')

 

 

🚀결과🚀

 

 

✨Point✨

"분자/분모" 형태로 나타내는 방법
1. print("%d/%d"%(top,bottom))
2. print(top,'/',bottom, sep='')

 

출력형태 결과 비교