pendant.dev

[백준/Python] 1193번 : 분수찾기

pendant.k's photo
pendant.k
·

2 min read

문제

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

  • 표에 나열된 분수의 규칙을 찾아서 주어지는 X번째에 위치하는 분수를 출력하는 문제이다.

풀이

초반에 규칙을 찾는 데 시간을 생각보다 많이 썼다. 규칙을 찾기 위해서 주어진 예시를 나열해보는 것을 습관화하는 게 좋을 것 같다.

규칙만 찾고 나면 풀이는 간단하다. 각 대각선을 하나의 그룹으로 생각하고 몇 번째 라인의 몇 번째 값인지를 찾으면 된다.

line 1 : 1/1

line 2 : 1/2 2/1

line 3 : 3/1 2/2 1/3

...

풀이과정

  1. 먼저 주어진 번호가 몇 번째 라인에 속하는지를 구하였다.

  2. 짝수 번의 라인과 홀수 번의 라인은 서로 다른 규칙을 가지고 있으며 이에 따라서 라인 번호가 짝수인 경우와 홀수인 경우를 나누어 값을 구하였다.

  3. 나는 예시 그림을 그대로 본따서 라인 별로 (분자 , 분모) 형태의 튜플을 값으로 가지는 리스트를 만들어서 그 중 구해야하는 값의 인덱스를 구하는 방식으로 문제를 풀었다.

X = int(input())
temp = 0

# Find Line
line = 1
temp += X
while True:
    temp -= line
    if temp > 0:
        line += 1
    else:
        break

ls = []
cnt = 0

for j in range(line):
    cnt += j

if line % 2 == 0:
    # 짝수 라인은 위에서부터 아래로

    for i in range(line):
        ls.append((i+1, line-i))
else:
    for i in range(line):
        ls.append((line-i, i+1))

point = X-cnt - 1
x, y = ls[point]
print(f'{x}/{y}')

후기

다른 사람들의 풀이를 보니 point를 따로 구하지 않고 즉각적으로 해당 지점의 분수를 구하는 경우가 많았다. 남들에 비해서 조금 돌아가는 방법인듯하다. 굳이 list를 만들 필요도 없는 것 같다. 더 삽질하지 않고 최적화된 코드를 작성할 수 있도록 열심히 공부해나가야겠다.

Python