[python_파이썬]백준_1193번_분수찾기_풀이

공부하는허딩크 : https://www.youtube.com/live/OlQbmK-38aQ?feature=shared

 

이것도 어렵네...

문제 자체도 이해못해서 지그재그의 과정도 다른 풀이를 참고했다.

아래의 코드도 스스로 풀지는 못했고, 다른 풀이를 참조했으나 첫번째 코드는 시간초과가 발생했다.

import sys

input = sys.stdin.readline

N = int(input())

# 시간초과

cnt = 1

temp = 1

a = 1

b = 1

answer = 1

while N > temp:

    cnt += 1

    temp += cnt

for i in range(2, cnt + 1):

    if i % 2 == 0:

        b += 1

        answer += 1

        if answer == N: break

        for _ in range(i-1):

            a += 1

            b -= 1

            answer += 1

            if answer == N: break

    else:

        a += 1

        answer += 1

        if answer == N: break

        for _ in range(i-1):

            a -= 1

            b += 1

            answer += 1

            if answer == N: break

   

print("{}/{}".format(a, b))

 

기본 while문 조건 찾는 것 부터가 난관이 발생했다.

 

내가 생각한 방향은 일단 구역을 1, 2, 3, 4, 5------ 구역으로 나누어 N이 나올때 해당 숫자의 구역을 찾는다.

예를 들어, N = 2, 3이면 2구역, N = 4, 5, 6이면 3구역... 이렇게 while문으로 cnt를 구역변수로 구했다.

 

그 다음 for문으로 구역별 짝수 구역일때는 분모 +1, 홀수 구역일때는 분자 +1의 조건을 주고,

또 각 구역 안에서 각 구역의 개수만큼 짝수일때는 분자 +1, 분모 -1, 홀수일때는 분자-1, 분모+1의 조건을 주었다.

 

그리고 answer = 1을 주어 내가 지정한 N이 도달할때 break를 줘서 그 시점 a와 b를 출력하게끔 작성하였다.

 

그런데... 시간초과..... 

 

두번째 chat gpt에 물었다. 근데... 이게 진짜 이해가 안된다.

N = int(input())

# 대각선 번호 계산

diagonal = 1

while N > diagonal:

    N -= diagonal

    diagonal += 1

# 짝수 대각선인 경우

if diagonal % 2 == 0:

    numerator = N

    denominator = diagonal - N + 1

# 홀수 대각선인 경우

else:

    numerator = diagonal - N + 1

    denominator = N

print("{}/{}".format(numerator, denominator))