Baekjoon 문제 풀기 (1193번 : 분수찾기) Python

1193번 : 분수찾기

1. 문제읽기

---

규칙찾기

문제의 규칙은 찾았는데 코드로 구현하는 것이 너무 어려웠다.
내가 제일 어려워하는 방법의 구현 문제였다.
X번째 수가 몇번째 그룹에 속하는지를 찾으면 쉽게 풀 수 있다.
python으로 제출했는데 시간초과가 떠서 pypy3으로 출력했더니 성공했다.
맞았지만 다음에 다시 풀어봐야겠다..

2. 제출 코드

---

예를 들어 8번째 수를 찾는다고 했을 때, 8번째 수는 1+2+3 하고 4번째 그룹의 2번째 수가 된다.
나는 이 로직을 반복문을 구현해서 푸는 것이 최선이였다.
시간초과가 날 것 같았지만 그래도 끝까지 해보느라 변수도 뒤죽박죽인 이상한 코드가 완성됐다.

헤멨던 가장 큰 이유는 나는 1, 2, 4, 7 처럼 라인의 첫번째 숫자보다 클 때 X의 값을 구하려고 했는데 X의 값이 계속 1, 2, 4, 7보다 크기 때문에 반복문을 구현하기가 어려웠다.
바꿔서 끝 값보다 커지기 전 값을 알아내면 쉬웠을 것 같다.

t = int(input())
tmp = 0
total = 0
for i in range(1, t+1):  # t=8
    if t > i*(i+1)/2:
        tmp = max(tmp, i)

row = tmp+1  # row=4
total = int(tmp*(tmp+1)/2)

minus = t - total  # 4줄의 2번째
row_2 = 1
for i in range(1, minus):  # minus만큼 반복  2번반복
    row -= 1
    row_2 += 1

if (tmp+1)%2 == 1:  # 홀수면
    print(f"{row}/{row_2}")
elif (tmp+1)%2 == 0:
    print(f"{row_2}/{row}")

3. 공부할 것

---

규칙은 단순하다. X가 몇번째 라인에 있는지, 몇번째 수인지를 찾는다.
그 다음 그 라인이 짝수인지 홀수인지에 따라 +1 과 -1을 해주면 된다.

정답 코드를 보니 line과 end 변수를 이용해서 문제를 풀었다.
먼저 1, 3, 6, 10 … 이런식으로 마지막 라인의 숫자를 구해보면 2, 3, 4 씩 증가하는 것을 알 수 있다.

1번째 라인은 1개의 숫자, 2번째 라인은 2개의 숫자, 3번째 라인은 3개의 숫자 이렇게 증가하므로
line은 1씩 증가시켜주고 end에는 line값을 증가시켜주면 두 가지 규칙을 모두 만족하게 된다.
구하려는 숫자 X가 end(라인의 마지막 숫자)보다 작으면 반복문을 종료시킨다.

짝수, 홀수에 따라 line/1값에서 n값을 더해주고 빼주고 하면 답이 출력된다.

x = int(input())
line = 0
end = 0

while x > end:
    line += 1
    end += line

n = end - x
if line%2 == 0:  # 짝수면
    print(f"{line-n}/{1+n}")
else:
    print(f"{1+n}/{line-n}")