[백준] 1193번 문제 (분수찾기) 파이썬(Python) 풀이

문제 내용

# 분수 찾기 문제
# key point :
# 1. 몇번째 대각선인지..
# 2. 대각선이 좌/우측 어디로 향하고 있는지
# crossNum : 몇번째 대각선인지 알려주는 변수
# check : 해당 대각선의 최대 번호

crossNum = 1
counter = 2
check = 1
n = 0

for _ in range(int(input())):
    n += 1
    if check < n:
        check += counter
        counter += 1
        crossNum += 1
down = crossNum
up = 1

# 우측으로 향하는 대각선의 경우
if crossNum % 2 == 1:
    for _ in range(check - n):
        up += 1
        down -= 1

# 좌측으로 향하는 대각선의 경우
else:
    tmp = up
    up = down
    down = tmp
    for _ in range(check - n):
        up -= 1
        down += 1
print("%d/%d" % (up, down))

내가 작성한 코드

 

사실 처음에는 어떻게 풀어야 될 지 막막했는데

규칙이 어떻게 될까 계속 생각해봤다..

 

우선 입력에 대한 결과로 알아야 될 게 크게 2가지 정도가 있다.

 

1. 몇번째 대각선인지..

몇번째 대각선일까

이런식으로 대각선이 하나 증가할때마다 이전 대각선의 분수의 수 +1을 해주면 해당 대각선이 몇개의 분수를 가지고 있는지 알 수 있고 1행의 분자는 항상 1이고 분모는 해당 대각선의 번호가 된다는 규칙을 알 수 있다.

 

 

2. 대각선이 우측으로 향하는 대각선인지 좌측으로 향하는 대각선인지..

대각선이 향하는 방향

1번의 대각선의 순서를 알게 됐으면 이제 해당 대각선이 어느 방향으로 향하는 대각선인지만 알면 매우 정답에 근접했다고 볼 수 있다. 

우선 대각선의 방향을 구하는 방법은 매우쉽다 1행의 분모가 홀수면 우측 위로 향하는 대각선 .. 짝수면 좌측 아래로 향하는 대각선이 된다.

 

이제 1번 힌트와 2번 힌트를 조합하면 쉽게 정답을 구할 수 있다.