< 문제 >
https://www.acmicpc.net/problem/1193
1193번: 분수찾기
첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다.
www.acmicpc.net
< 규칙 >
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/6 2/5 3/4 4/3 5/2 6/1
7/1 6/2 5/3 4/4 3/5 2/6 1/7
짝수(짝수번째 줄)는 분모가 큰 것으로 첫 분수를 시작합니다.
반대로, n = 홀수는 분자가 분모보다 큰 수로 시작을 합니다. 분모 혹은 분자가 큰 수로 시작을 한다면 마지막에는 1이 되고, 작은 값으로 시작을 한다면 마지막에는 n의 값이 되는 규칙을 볼 수 있습니다.
첫 시작에 point를 둬야 하는데, 첫 시작의 분모나 분자가 2 혹은 3이라면 2일때는 2개의 경우가 존재하며, 3일 때는
3개의 분수의 경우가 존재합니다.
< 첫 구현 >
< FAIL >
N = int(input())
n = 1
sum = 0
while sum < N:
sum+=n
n+=1
n-=1
if n%2!=0:
y = n
x = 1
print(y-(N-sum-1),'/',x+(N-sum-1),sep ='')
else:
y = 1
x = n
print(y+(N-sum-1),'/',x-(N-sum-1),sep = '')
< PASS >
N = int(input())
n = 1
sum = 0
while sum < N:
sum+=n
n+=1
n-=1
sum-=n
if n%2!=0:
y = n
x = 1
print(y-(N-sum-1),'/',x+(N-sum-1),sep ='')
else:
y = 1
x = n
print(y+(N-sum-1),'/',x-(N-sum-1),sep = '')
만약 N = 14라면 while 문을 빠져나왔을때의 기준으로 N = 14, sum = 15, n = 6의 값이 될 것입니다.
그래서 알맞은 n값을 찾기 위해 n-=1을 해주었고, 현재 누적된 원래의 sum값은 sum - n 이기에 위와 같이 코드를 작성하였습니다. ( sum값이 누적된 번호의 역할을 한다고 생각하면 됩니다. )
홀수 일 때와 짝수일 때가 분모 분자의 시작 크기가 다르므로 위와 같이 if else문으로 나누어 보았습니다.
n = 5일 때의 홀수 5번째의 분모 시작 값은 5/1입니다. 11번 분수이고, 우리가 찾고자 하는 것은 14번 분수입니다. 14번 분수와는 분자로 -3, 분모로 +3이 차이가 나므로 위와 같이 코드를 작성해보았습니다.
< 느낀점? >
처음에는 문제의 지그재그란 말에 집중해 그림을 보고 어떻게 이게 지그재그인가?라는 생각을 했었습니다. 그래서 다른 분들이 푸신 코드를 봐도 거기에 집중을 하지 못했었습니다. ( 제 머릿속에는 그림과 지그재그뿐이었습니다... ) 그렇게 한 달 정도 생각이 날 때마다 봤고, 문제를 풀 때 차분하게 생각을 해봐야겠다는 생각이 들어 생각을 했더니 분모 x 분자 y로 풀면 괜찮겠다는 생각이 들어 풀이를 작성하게 되었습니다. 앞으로는 조금 더 차분하게 문제를 끝까지 읽고 신중히 생각할 수 있도록 해야겠습니다.
