[백준/Python]24267: 알고리즘의 수행 시간 6

문제

https://www.acmicpc.net/problem/24267

알고리즘 수업 시리즈 중 가장 어려웠던 문제다. 수학책을 다시 구해봐야겠다.

서준아 그만 일하자

---

풀이

N = int(input())
print(N*(N-1)*(N-2) // 6, 3, sep="\n")

이 문제는 두가지 방식으로 풀 수 있다. 압도적으로 쉬운건 조합을 이용한 풀이다.

 

시그마 공식을 이용한 풀이

숫자의 개수: n-2개 (1부터 n-2까지니까)
첫 번째 숫자: 1^2 = 1
마지막 숫자: (n-2)^2

 

1부터 n까지의 제곱의 합 공식 = n(n+1)(2n+1) / 6

 

∑(k(k + 1) / 2)를 풀어서 정리하는 과정:
먼저, k(k + 1) / 2를 전개, (k^2 + k) / 2
이걸 시그마 식에 넣으면 ∑((k^2 + k) / 2)
시그마는 선형 연산이기 때문에, 각 항을 따로 계산할 수 있다.
∑(k^2 / 2) + ∑(k / 2)

이제 각 시그마 항을 계산해 보자.

∑(k^2 / 2), 여기서 k는 1부터 n-2까지.
= ((n-2)(n-1)(2n-3) / 6) / 2
= (n-2)(n-1)(2n-3) / 12

∑(k / 2), 여기서 k는 1부터 n-2까지.
= ((n-2)(n-1) / 2) / 2
= (n-2)(n-1) / 4

이제 이 둘을 더하면
(n-2)(n-1)(2n-3) / 12 + (n-2)(n-1) / 4

통분하면
((n-2)(n-1)(2n-3) / 12) + (3(n-2)(n-1) / 12)

괄호를 풀고 정리하면
(n-2)(n-1)(2n-3 + 3) / 12
= (n-2)(n-1)(2n) / 12
= n(n-1)(n-2) / 6

따라서, ∑(k(k + 1) / 2)는 n(n-1)(n-2) / 6로 정리될 수 있다.

 

조합을 이용한 풀이

n = 7이라고 가정했을때, 코드의 실행 순서는 다음과 같다. 순서대로 i j k 다.

123 124 125 126 127
134 135 136 137
145 146 147
156 157
167

234 235 236 237
245 246 247
256 257
267

345 356 357
356 357
367

456 457
467

567

잘 보면 1부터 7까지의 숫자 중에서 3개를 선택하는 경우의 수와 같다.
즉, nC3이 되는 셈이다.

참고로 nCr을 계산하는 공식은 아래와 같다.
nCr = n! / (r! * (n-r)!)

 

우리는 nC3이니까 아래와 같이 계산하면 된다.
nC3 = n! / (3! * (n-3)!)
nC3 = n! / (6 * (n-3)!)

여기서 n!은 n! = n * (n-1) * (n-2) * (n-3)! 이 되니까,
nC3 = (n * (n-1) * (n-2) * (n-3)!) / (6 * (n-3)!)

분자, 분모 공통으로 존재하는 (n-3)!을 약분해서,
nC3 = (n * (n-1) * (n-2)) / 6 가 된다.

 

참고

https://aplight.tistory.com/41?category=1060356

[백준/python] 24267 알고리즘수업-알고리즘의수행시간6: 조합

조합 사용

 

https://yuria.dev/post/187

백준 24262~24267. 알고리즘의 수행 시간 1~6 정리

시그마 계산