[파이썬] 백준 1193번 「분수찾기」

문제

백준 1193번/실버5

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

1193번: 분수찾기

 

 

 

문제해설

글로 봐도 이해가 바로 가기는 할텐데, 그림같은 순서대로 갈 때, n번째에는 어떤 분수인지 출력하는 문제이다.

 

 

 

풀이 전략

대각선의 순서를 i라고 하자.

1번째 대각선에서는 1개, 2번째 대각선에서는 2개, 세 번째 대각선에서는 3개, i번째 대각선에서는 i개의 분수가 존재한다. 즉 i번째의 순서는 1+2+3+...(i-1)  +1 부터 시작하여 1+2+3+...+i 에 끝난다. 

n이 몇 번째 대각선에 있는지 1부터 i까지의 합 공식 i*(i+1)/2 를 이용하여 i를 구하고, i의 시작지점, i의 끝지점까지 반복하면서 n번째에는 어떤 분수가 있는지 구하면 된다.

단, i가 짝수일 때는 1/i 로  시작하여 분모는 -1씩, 분자는 +1씩 늘어다는 규칙이고,

i가 홀수 일때는 i/1로 시작하여 분모는 +1씩, 분자는 -1씩 줄어든다는 규칙이므로, i를 구하고, i의 홀수 짝수 여부에 따라서 분모 분자가 정해지고 n까지 어떻게 분수가 바뀌는지 파악해주면 되는 문제이다.

 

 

코드

import sys;

n = int(sys.stdin.readline().rstrip()); #n입력

#몇 번째 라인에 있는지 계산
i = 0; #분자 또는 분모의 최대값 계산하는 변수
end = 0; #분자 또는 분모가 최대일 때의 몇 번째 번호
while i*(i+1)//2 < n :
    i+=1;
    end+=i;

# 시작지점 번호, 순서
start = end - i+1;


#i가 짝수일때
if i%2 == 0:
    child = 1; #분자가 1
    parent = i; #분모가 i 
    while start < n:  #n보다 작을 때동안 분모-1, 분자+1
        start+=1;
        parent -=1;
        child +=1;
        
#i가 홀수일 때
else: 
    child = i; #분자 i
    parent = 1; #분모 1
    while start < n: #n 보다 작을 떄 동안 분모+1, 분자 -1
        start+=1;
        parent +=1;
        child -=1;
        
        
print(f"{child}/{parent}") #출력

 

 

 

결과

 

 

고찰

규칙만 잘 찾으면 쉬우나, while 문 조건이 헷갈릴 수 있음.