Seongkyun Han's blog

190114 백준 알고리즘 문제풀기

14 Jan 2019 | baekjoon

Baekjoon 알고리즘 문제풀기

[1193] 분수찾기

문제

  • 1/1 -> 1/2 -> 2/1 -> 3/1 -> 2/2 -> … 과 같이 지그재그 순서로 차례대로 1번, 2번, 3번, 4번, 5번, … 분수라고 정의

  • 입력 N에 대해 N번째 분수를 구하는 프로그램 작성

  • 너무 어렵게 푼 듯 하다.
  • 우선 몇 번째 그룹에 속해있는지 구하고, 그 그룹의 첫 번째 항의 순서를 구한 후 그룹 내의 결과 찾아 출력하는 형식이다.
  • 그 그룹의 첫 번째 항을 구할 때 계차수열의 합의 공식을 사용하였다.
    • 각 그룹의 첫 번째 순서는 1, 2, 4, 7, 11, …의 순서를 보인다.
    • $a_{n+1}=a_{n}+n$ 이므로, $b_{n}=a_{n+1}-a_{n}$ 으로 정의하고 $a_{n+1}-a_{n}=n$ 이므로 $b_{n}=n$ 이 성립한다.
    • 따라서 $a_{n}=a_{1}+\sum_{k=1}^{n-1}b_{k}=1+\sum_{k=1}^{n-1}k$ 의 관계가 성립한다.
    • 합의 공식에 따라 계산을 하면,
    • $a_{n}=a_{1}+\sum_{k=1}^{n-1}b_{k}= 1+\sum_{k=1}^{n-1}k \ =1+\sum_{k=1}^{n-1}k= 1+\frac{(n-1)\times n}{2}$
    • ∴ $a_{n} = \frac{(n-1)}{2}\times n +1$

정답

def find_group(n):  # 입력된 숫자가 몇 번째 그룹에 속해있는지를 찾는다.
    cnt = 0
    if n==1:
        return 1
    else:
        for j in range(1, n+1):
            cnt += 1
            n -= j
            if n == -cnt:
                return cnt-1
            elif n<0:
                return cnt

num = int(input())
group = find_group(num)
odd = group % 2 # 홀/짝별로 숫자배열이 달라지므로 다른 연산이 필요하다.
nums = [] # 해당 그룹의 숫자들을 저장한다.
if odd==1:
    temp = group
    for j in range(1, group+1):
        string = str(temp) + '/' + str(j)
        nums.append(string)
        temp -= 1
else:
    temp = group
    for j in range(1, group+1):
        string = str(j) + '/' + str(temp)
        nums.append(string)
        temp -= 1
init_num = int((group-1) * group / 2 + 1) # 앞에서 정의된 일반항으로 해당 그룹의 첫 번째 순번이 몇 번으로 시작하는지를 찾는다.
plus = num - init_num # 완성 된 분수 그룹에 몇 번째 숫자인지를 정의한다.
print(nums[plus])

Related Posts