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

Dev_ch·2023년 3월 17일
1

이 문제는 이해하는데 상당히 어려웠다, 특히 문제가 지그재그의 순서를 애매(?)하게 알려줘서 해당 순서를 찾아야했는데 순서는 아래 사진과 같았다.

해당 순서를 토대로 배열을 만든다고 가정하면

1/1
1/2, 2/1
3/1, 2/2, 1/3
1/4, 2/3, 3/2, 4/1
5/1, 4/2, 3/3, 2/4, 1/5
.
.
위와 같은 순서로 계속 반복될 것 이다.

💡 여기서 줄 마다 특징을 찾아보면
짝수 라인 : 분모가 1씩 늘어나고 분자가 1씩 줄어듦
홀수 라인 : 분자가 1씩 늘어나고 분모가 1씩 줄어듦

이제 규칙을 찾았으니, 몇번째 줄에 몇번째 위치의 분수가 무엇인지 알아내면 된다.

while num > line:
    num -= line
    line += 1

위의 해당 loop를 사용해 몇번째 줄이고 몇번째 위치인지 알아 낼 수 있다.
만약, 5번째 인덱스 값을 찾는다면

num line
5 1
4 2
2 3 이 되면서 루프문이 종료될 것 이다.

# 짝수일경우
if line % 2 == 0:
    a = num
    b = line - num + 1
# 홀수일경우
elif line % 2 == 1:
    a = line - num + 1
    b = num

print(f'{a}/{b}')

홀수인 경우 분자가 늘어나고 분모가 줄어들기에 분모인 a는 line - num + 1 을 해준 값인 2 그리고 분자는 num 값을 그대로 사용해주었다.

🤔 line - num + 1을 하면 어떻게 해당 값이 나오는건가요?

line - num + 1은 대각선에서 분수의 위치에 따라서 분자 또는 분모를 계산하기 위해 사용되는 식이며 이 값이 a이냐 b이냐에 따라 분자와 분모를 결정하게 된다.

전체코드

num = int(input())
line = 1

while num > line:
    num -= line
    line += 1
    
# 짝수일경우
if line % 2 == 0:
    a = num
    b = line - num + 1
# 홀수일경우
elif line % 2 == 1:
    a = line - num + 1
    b = num

print(f'{a}/{b}')
            
profile
내가 몰입하는 과정을 담은 곳

0개의 댓글