백준(파이썬, python) - 1193번 분수찾기

1. 1193번

 

1) 문제

 

2) 풀이

import sys
x = int(sys.stdin.readline())
i = 1
n = 1

while x > n:
    i +=1
    n += i
k = n-x+1
if x == 1:
    print("1/1")
elif i%2 ==0 :
    print("{0}/{1}".format((i+1-k),(k)))
    
else:
    print("{0}/{1}".format((k),(i+1)-(k)))

 

3) 문법 및 풀이과정

- 문제 이해

이 문제도 벌집처럼 군수열로 이해할 수 있다. 다만 짝수번째 군과 홀수번째 군에 차이가 있어 최종적으로 출력할 때 이를 구분하여 출력해야할 것이다.

 

1군 : 1/1

2군 : 1/2 , 2/1

3군 : 3/1, 2/2, 1/3

4군 : 1/4, 2/3, 3/2, 4/1 

....

 

이 때 각 군에 들어있는 항의 개수는 1개씩 증가하여 n군에는 n개의 항이 들어있다. 따라서 x번째 항이 궁금하다면 k가 1+2+3+...+n보다 작아지는 첫번째 n값을 구하면 k가 몇번째 군의 원소인지 알아낼 수 있다.

또한 n번째 군의 모든 분수는 분자+분모 = n+1 이라는 규칙도 발견할 수 있다.

짝수군과 홀수군의 차이를 살펴보면 짝수번째 군은 분자가 1부터 시작하여 커지는 반면, 홀수번째 군은 분모가 1부터 시작하여 1씩 커지는 것을 알 수 있다.

 

위 성질들을 이용해 코드를 짜보자.

 

- 문제 풀이

(1) 입력값 x를 받는다.(sys 활용 , 시간 초과 방지)

(2) n, i를 1로 정의한다. 이 때 n은 각 군의 마지막 항의 번호(n군의 항들 중 마지막 항, 즉 n(n+1)/2번째 항)를 의미하고 i는 군의 번호가 될 것이다.

(3) x>n일 동안 while문을 작성한다. 즉, n이 x보다 커지는 그 순간 while문이 중단되어 그 때의 n의 값과 i값을 활용할 것이다.(이 때의 n과 i가 i번째 군과 i번째 군에 속하는 마지막 항은 n번째 항임을 의미한다.)

(4) if문을 통해 i=1/짝수번째 군일 때/홀수번째 군일 때를 나누어 출력하도록 한다.

짝수번 군일 때,

분모가 1 부터 시작한다. 

k = n-x+1이라 두면(해당 군 내에서 몇번째 항인지를 알기 위함이다. x와 n은 전체 수열에서의 항의 번호이므로 각 군의 내에서 몇번째인지를 아는 것이 필요하다.), k는 각 군의 마지막 항에서부터 셀 때의 값이다. 

예를 들어, x=9이면 n=10이 된다. 이 때 k = 10 - 9 +1 = 2이다. x=9이면 4군에 해당되고 4군에는 ( 7, 8, 9, 10)번째에 해당되는 항들이 있다. 이 중 9는 뒤에서 두번째의 항에 해당된다. k값이 바로 이 두번째 항임을 의미한다. 

 

이부분이 헷갈린다면 k = (i+1) - (n-x+1) 로 두는 것이 좋겠다.(우선 나는 코드를 짜 둔대로 k = n-x+1로 두고 설명을 진행하겠다.)

따라서 짝수번째 군일 때는 분자를 (i+1)-k로 분모를 k로 표현되도록 하고, 홀수번째 군은 분자와 분모를 반대로 표현한다.

k는 뒤에서부터 세는 것이므로 짝수번째일 때는 분모를 뒤에서부터 세고, 홀수번째 군은 분자를 뒤에서부터 센다고 생각하면 된다.