백준 1193번 풀이

문제

이런 표가 있고 움직이는 패턴이 있을 때, 몇번째 분수가 뭔지 찾는 것. 패턴은 풀이란에 넣어드림. 참고로 오늘 쓰는 건 근의 공식밖에 없으므로 따로 설명을 넣거나 하지는 않습니다.

풀이

움직이는 패턴이 이런 식이다. 보자마자 마른세수 마렵다면 지극히 정상이다. 나도 그랬음. 이건 수능에 실렸으면 저기 어디 중간 페이지에는 나왔을 문제다. 공명의 함정은 아니지만 일단 당황하지 말고, 저기에 있는 패턴을 파악해보자.

봐도 모르겠다고? 일단 여기서 패턴은 크게 두 개인데

1. 분자와 분모의 패턴
2. 줄간 패턴

이렇게 있다. 그럼 굵직한 패턴부터 보고 가자.

줄간 패턴

줄간 패턴은 크게 두 개인데, 전체적으로 줄의 번호 수(n)만큼 분수를 가지고 있으며 각 줄의 시발점(욕 아님)과 종점의 분자 혹은 분모가 해당 줄 번호이다. 세번째 줄을 보면 분수가 총 3개이고, 시발점의 분자와 종점의 분모가 3이다. 그리고 줄의 누적합은 순서대로 1, 3, 6, 10, 15, … 이다. 이건 초항이 1, 공차가 1인 등차수열의 각각 1, 2, 3, 4, 5번째까지의 합이고, 줄에 있는 분수의 수도 실제로 초항이 1, 공차가 1인 등차수열.

분수의 패턴

이거는 홀수번째 줄과 짝수번째 줄의 패턴이 반대인데, 세번째 줄은 분자가 큰 수에서 하나씩 감소하고 분모가 작은 수에서 큰 수로 하나씩 증가한다. (분자가 3, 2, 1이고 분모가 1, 2, 3) 짝수번째 줄은 반대로 분자가 작은 수에서 하나씩 증가하고 분모가 큰 수에서 하나씩 감소한다.

등차수열

솔직히 여기까지 봐도 근의 공식이 뭔 상관인지 모르겠지들? 그럼 뜬금포로 왜!!! 근의공식!!! 2에이분의 마이나쓰 비 플마 루트 비제곱 마이나쓰 4에이씨가 나왔는지 설명을 할 건데… 줄간 패턴에서 각 줄의 분수 숫자가 초항이 1이고 공차가 1인 등차수열이고 분수의 총 개수가 해당 등차수열의 합계라고 했다. 아니 스크롤도 안 넘겼어 그걸 까먹으면 어떡함… 아무튼, 등차수열의 일반항… 그러니까 이 문제에서 n번째 줄의 분수 개수(an)를 구하는 공식은

이거다. 여기서 a_1=1, d=1을 대입하고 풀면 a_n=n이 된다. 즉, n번째 줄의 분수 개수는 n개이다. 그리고 초항이 a_1, 공차가 d인 등차수열의 a_n항까지의 합은

이거다. 여기다가도 마찬가지로 a_1=1, d=1을 대입해보면 최종적으로

이 식을 도출할 수 있다. 즉, 저 식이 =0일때를 상정하고 근의 공식에 넣는거고, 우리가 입력하는 숫자 N은 앞의 문제와 마찬가지로 ‘또’ =0에서 0을 빼고 거기에 들어갈 거라 이항정리가 필요한데…

예시로 딱 나눠 떨어지는 10을 가져왔다. 그럼 여기서 어떻게 푸느냐… 2차, 1차 항의 계수를 1/2로 놓고 풀던가(이 경우 상수항은 그냥 넘어가면 장땡이라 편함), 양변에 2를 곱해 분모를 치워버리던가(2차, 1차 항의 계수가 1이 되고 상수항에 곱하기 2를 한다). 본인은 후자요.

import sys
import math
a = int(sys.stdin.readline())
c = a * -2
# 이제 이거 없으면... 섭하죠? 
line=int(-(-(-1 + math.sqrt((1 * 1) - 4 * 1 * c)) // 2))
print(line)

줄 수는 이런 식으로 도출하면 된다. 저기서 합계가 아닌 숫자, 그러니까 11, 12, 18 이런 숫자들은 소수점에 뭐가 붙는데, 그걸 일단 떼버리면 줄 번호가 된다. 11, 12는 10보다 크니까 5번째 줄에 있을거고 18은 5보다 크니까 6번째 줄에 있다.

import sys
import math
a = int(sys.stdin.readline())
c = a * -2
# 이제 이거 없으면... 섭하죠? 
line = int(-(-(-1 + math.sqrt((1 * 1) - 4 * 1 * c)) // 2))
# 몇 번째 줄?
maxline = sum(list(range(1,line+1)))
minline = sum(list(range(1,line)))+1
# 그 줄의 최댓값과 최솟값
gap = a - minline
# 줄의 최댓값과 내가 가진 값의 차이는? 
if line % 2 == 0:
    bunja = gap + 1
    bunmo = line - gap
else: 
    bunja = line - gap
    bunmo = gap + 1
print('{0}/{1}'.format(bunja,bunmo))

일단 변수의 의미부터 보고 갑시다.

Maxline: 그 줄의 최댓값(초항이 1이고 공차가 1인 등차수열의 n번째 줄까지의 합)

minline: 그 줄의 최솟값(초항이 1이고 공차가 1인 등차수열의 n-1번째 줄까지의 합+1)

예를 들어서 5번째 줄이면 Maxline은 1+2+3+4+5 해서 15, minline은 (1+2+3+4)+1 해서 11이다. 이걸로 그 줄의 최댓값과 최솟값을 찾게 되는 것. 아직까지는 줄을 찾은거고, 이제 실질적으로 이게 몇번째인지를 찾아야 하는데 그 역할을 하는 변수가 gap이다. 예를 들어서 13번째 분수를 찾는다고 하면, 13은 11보다 2 크기 때문에 5번째 줄의 최솟값(11)에서 두 개 떨어진다.

로직 부분은 간단하다. 짝수줄의 경우 분자가 증가, 분모가 감소이고 홀수줄은 짝수랑 반대. 예를 들어서 12를 입력했다, 그러면 gap이 1이 되는데

1) line(줄 번호)은 5이므로 2로 나누었을 때 나머지가 1이다.

2) 분자는 5-1을 해 주고, 분모는 1+1을 해 준다. (gap에 하나 안 더하면 각 줄의 첫번째는 분모나 분자가 0이 된다)

3) 따라서 4/2가 나온다.

이렇게 된다. …솔직히 나도 이거 한번에 맞을 줄 몰랐음…ㅋㅋㅋㅋ