백준 1193 풀이

기존에 코드를 작성했지만 [1,1]부터 차례로 하나씩 증가시키며 동작하도록 만들었다. 문제가 없다고 판단했지만 제출시에 시간초과가 떴다. 그래서 좀더 빠르게 타겟의 값을 가져오는 방법을 고민했다.

 

그래서 생각한것이 타겟에 가까운 인덱스를 빠르게 찾고, 해당 블럭안에서 값을 찾는 방법이다.

즉, 1/1 -> 1/2 -> 2/1 -> 3/1 -> 2/2 -> 1/3 -> 1/4 -> 2/3 -> 3/2 -> 4/1을 블록단위로 나눌수 있다.

즉, (1/1) -> (1/2 -> 2/1) -> (3/1 -> 2/2 -> 1/3) -> (1/4 -> 2/3 -> 3/2 -> 4/1)

 

따라서 해당 블록이 몇 번째인지 파악하는 식을 구해야한다. 솔직히 문과라서 동작과정은 이해했는데 식으로 짜기가 오래걸렸다......ㅎㅎ

 

그래서 결론은 블록 마지막 인덱스를 end라고 했을때 다음 블록 인덱스까지 N만큼 증가한다.

예를 들어 1, 3, 6, 10이 각 블록의 마지막 인덱스인데 +2, +3, +4씩 증가한다. 이것은 add라고 칭한다.

그러면 add는 결국 블록 자체의 인덱스가 된다. 즉 1이면 1이고 +2를 해서 얻는 인덱스 3은 2번째 블록에 해당한다. 또한 +3을 해서 얻는 인덱스 6은 3번째 블록에 속하는 식이다.

따라서 add와 end를 통해 블록의 첫번째 인덱스인 start를 찾을수 있다.

즉, add가 3이고 end가 6인경우 start는 6-3+1 = 4인 것이다.

 

또한 add가 짝수인지 홀수인지를 판단하여 start에 해당하는 값을 구하는게 가능하다. 

예를 들어 add가 3이고 start가 4인경우 add가 홀수이기 때문에 값은 3/1이 된다.

만약 add가 4라면 1/4인 것이다.

 

그럼 반복문을 통해 start부터 n까지 반복하며 뒤를 뺄지 앞을 뺄지 결정하며 실행하면 된다.

n = int(input())

end = 0
add = 0
while(end < n):
    add += 1
    end += add

start = end - add + 1
target = [0,0]
if add % 2!=0:
    target[0]=add
    target[1]=1
else:
    target[0] = 1
    target[1] = add

for i in range(start, n):
    if add %2 != 0:#홀수인경우
        target[0] -= 1
        target[1] += 1
    else:
        target[0] += 1
        target[1] -= 1
print(str(target[0])+"/"+str(target[1]))