[Baekjoon][Python] 1193 분수찾기

 

분수찾기 문제.

규칙을 찾는 것이 어려웠다.

처음에 시간복잡도 생각없이 WHILE 반복으로 처리하다가 시간복잡도를 생각하고 처음부터 다시 풀었다.

문제 풀이 방법은 X가 주어졌을 때 X가 어떤 배열에서 시작되는지를 구해서 시작과 X의 차이만큼 분모, 분자를 계산해서 구했다.

 

예)  X = 14

 

1의 시작은 1/1

2의 시작은 1/2 

3의 시작은 3/1

4의 시작은 1/4 

와 같이 짝수면 가로로 홀수면 세로 끝에서 시작하여

 

 

 

 

세로에서 시작시 분자 - 1, 분모 +1

가로에서 시작시 분자 + 1 , 분모 - 1 로 진행한다.

세로 3/1 에서 시작시 3/1-> 2/2 -> 1/3

가로 1/4 에서 시작시 1/4-> 2/3 -> 3/2 -> 4/1 순.

 

시간 복잡도를 생각하여 입력된 X만큼 반복하는 것이 아니라

X보다 큰 최대 카운트를 찾았다.

즉 14가 입력되었을때 14의 가장마지막 끝인 15를 구했고 15까지 오는 카운트는 5라는 것을 구했다.

규칙은

1 -> 1

2 -> 2,3

3 -> 4,5,6

4 -> 7,8,9,10

.

.

 

이제 14의 시작점을 알았으니 시작점과 14의 분자, 분모 차이만 빼주고 출력하면 끝!

 

 

내 풀이