๋ฌธ์
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: ์กฐํฉ
๋ฌธ์ ์ค๋๋ ์์ค์ด๋ ์๊ณ ๋ฆฌ์ฆ์ ์ํ์๊ฐ ์์ ์กฐ๊ต๋ฅผ ํ๊ณ ์๋ค. ์๋น ๊ฐ ์์ ํ ๋ด์ฉ์ ํ์๋ค์ด ์ ์ดํดํ๋์ง ๋ฌธ์ ๋ฅผ ํตํด์ ํ์ธํด๋ณด์. ์ ๋ ฅ์ ํฌ๊ธฐ n์ด ์ฃผ์ด์ง๋ฉด MenOfPassion ์๊ณ ๋ฆฌ์ฆ ์
aplight.tistory.com
์กฐํฉ ์ฌ์ฉ
๋ฐฑ์ค 24262~24267. ์๊ณ ๋ฆฌ์ฆ์ ์ํ ์๊ฐ 1~6 ์ ๋ฆฌ
์ด ๋ฌธ์ ๋ค์ ์๊ณ ๋ฆฌ์ฆ ์คํ ์๊ฐ์ ๋ํด์ ์์๋ณด๊ธฐ ์ํ ๋ฌธ์ ์ด๋ค.ํ ๊ฐ์ ์์ ์๊ณ ๋ฆฌ์ฆ์ด ์ ์๋๋ฉฐ, ์ด ์๊ณ ๋ฆฌ์ฆ์ด ์ ๋ ฅ N์ด ์์ ๋, ์ํ ํ์๋ฅผ ๊ณ์ฐํ๊ณ ํ์๋ฅผ ๋คํญ์์ผ๋ก ๋ํ๋์ ๋
yuria.dev
์๊ทธ๋ง ๊ณ์ฐ