[백준 1193] 기본 수학 1 - 분수찾기

문제

무한히 큰 배열에 다음과 같이 분수들이 적혀있다.

1/1	1/2	1/3	1/4	1/5	…
2/1	2/2	2/3	2/4	…	…
3/1	3/2	3/3	…	…	…
4/1	4/2	…	…	…	…
5/1	…	…	…	…	…
…	…	…	…	…	…

이와 같이 나열된 분수들을 1/1 -> 1/2 -> 2/1 -> 3/1 -> 2/2 -> … 과 같은 지그재그 순서로 차례대로 1번, 2번, 3번, 4번, 5번, … 분수라고 하자.

X가 주어졌을 때, X번째 분수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다.

출력

첫째 줄에 분수를 출력한다.

 

 

 

풀이

 

우선 분수의 왼쪽 오른쪽을 a, b로 나누었다.

그리고 방향을 정하고 그 방향에 따라서 a와 b에 1씩 더할지 뺄지를 결정했다.

 

a,b=1,1
d=True 	#방향
for i in range(int(input())-1):
    if d==True:
        if a==1:
            b+=1
            d=False
        else:
            a-=1
            b+=1
    else:
        if b==1:
            a+=1
            d=True
        else:
            a+=1
            b-=1
print(a,"/",b,sep="")

잘 작동하였으나, 시간 초과가 뜨며 실패하였다. 큰 수를 입력할 경우, 반복 횟수가 크게 늘어나다 보니 발생하는 문제였다.

정상작동하지만 실패한 알고리즘

 

1  2  6  7  15 16 28 29
3  5  8  14 17 27 30
4  9  13 18 26 31
10 12 19 25 32
11 20 24 33
21 23 34
22 35
36

 

위와 같이 이동 순서를 정리해보았다.

맨 위의 표와 비교해 보면 한 가지 알 수 있는 점이 있었다.

1에서 시작하는 수직, 수평선은 1/x, x/1 꼴로 나타난다는 것이었다.

이것을 이용하여, 입력된 숫자에서 1씩 증가하는 값을 빼 주고, 값을 뺄 때마다 방향값을 바꿔 저장한 뒤, 마지막에 저장된 방향에 따라 입력된 숫자가 포함된 수직 or 수평선에서 1씩 증가하는 처리만 해주면 될 것이라 생각했다.

이런 식으로 불필요한 반복은 제거해주고, 만약 14가 입력된다면 11부터 14까지 한 번씩 반복하며 a와 b에 더하고 빼는 처리를 해 주는 것이다.

a,b,c=1,1,1		#c는 불필요한 반복을 제거하기 위해 사용
d=1			#방향
e=int(input())
while(e>0):
    e-=c		
    c+=1		#입력된 수에 c를 빼고, c에 1을 더한다.
    d=-d		#방향 전환
c-=1			
e+=c			#마지막에 저장된 c와 e에서 한 단계 물러준다.
if d==1:
    b=c
    for i in range(e-1):
        b-=1
        a+=1
else:
    a=c
    for i in range(e-1):
        b+=1
        a-=1
print(a,"/",b,sep="")

 

 

 

성공!