[백준] 24267: 알고리즘 수업 - 알고리즘의 수행 시간 6 - 파이썬[python]

와 이건 도저히 수식으로 구할 수가 없는 거다.. 결국 구글링을 했는데 시그마로 풀거나 조합으로 풀더라. 근데 솔직히 조합은... 실제로 떠올리기 힘들 것 같아서 패스하고 시그마를 이해해보려 했는데 풀이를 찾아볼 수가 없어서 ㅎㅎ.. 오랜만에 샤프를 들고 끄적이면서 시그마를 유도해 보는 데 성공했다.

코드

n = int(input())

print((n-2)*(n-1)*n//6)
print(3)

• 전의 코드에서는 (n-2)(n-1)n/6를 int로 감쌌는데, 어차피 몫만 반환하는 것이므로 //를 사용해도 된다.

풀이

1. 삼중 반복문을 풀자

i는 1~n-2만큼 반복돼서
j는 2~n-1, 3~n-1, ...,n-1~n-1만큼 수행되고
따라서 k는
3~n, 4~n, ..., n-1~n, n~n
4~n, ..., n-1~n, n~n
...
n~1, n~n
n~n만큼 수행된다.

2. 몇 번 수행되는지를 식으로 풀어보자

3~n은 n-2번, 4~n은 n-3번, ... n~n은 1번 수행되는 것이다. 즉,
3~n, 4~n, ..., n-1~n, n~n번 수행되는 것은 다시 말해
((n-2) + (n-3) + ... + 1)번 수행되는 것이고,

4~n, ..., n-1~n, n~n은
((n-3) + ... + 1)번 수행,
...
n-1~n, n~n은
(2+1)번 수행,

n~n은
(1)번 수행되는 것이다.

3. 수식으로 깔끔히 써보자

(n-2) + (n-3) + ... + 1 = $\displaystyle\sum_{x=1}^{n-2}{x}$ 이고,

(n-3) + (n-4) + ... + 1 = $\displaystyle\sum_{x=1}^{n-3}{x}$ 이고,
1 = $\displaystyle\sum_{x=1}^{1}{x}$ 이다.

따라서 k는 $\displaystyle\sum_{x=1}^{n-2}{x}$ + $\displaystyle\sum_{x=1}^{n-3}{x}$ + .. + $\displaystyle\sum_{x=1}^{1}{x}$ 번 수행되는 것이다.

이를 또 시그마로 예쁘게 정리하면 최종적으로 k는
$\displaystyle\sum_{k=1}^{n-2}{(\sum_{x=1}^{k}{x})}$ 번 수행되는 것이다.

이제 이 수식을 풀면 (n-2)(n-1)n/6이 나오게 된다. 시그마 공식은 몸이 기억하더라

3-1. 다른 방식으로 시그마를 만들어보자

✋🏻 여기서 잠깐! 2번으로 돌아가보자.

k는 ((n-2) + (n-3) + ... + 1) + ((n-3) + (n-4) + ... + 1) + ... + (2 + 1) + 1)번 반복된다고 했다.
여기서 또 규칙이 보인다.
바로 1은 (n-2)번 반복되고, 2는 (n-3)번 반복되고, ... (n-2)는 1번 반복되는 것이다.
즉, 총 (1(n-2) + 2(n-3) + 3(n-4) + ... + (n-2)1)번이 수행된다고 말할 수 있겠다.
이렇게 보면 이걸 어떻게 수식으로 정리하는데...? 싶었지만
1(n-2) + 2(n-3) + 3(n-4) + ... + (n-2)1 를 다시 써보면
1(n-1-1) + 2(n-1-2) + 3(n-1-3) + ... + (n-2)(n-1-n-2) 이다.
오호 그러면 이제 시그마로 나타낼 수 있겠다!
최종적으로 $\displaystyle\sum_{i=1}^{n-2}{i(n-1-i)}$ = $\displaystyle(n-1)\sum_{i=1}^{n-2}{i} - \sum_{i=1}^{n-2}{i^2}$으로 정리할 수 있게 된다.
마찬가지로 고딩 때 열심히 배운 시그마 공식으로 잘 풀면 (n-2)(n-1)n/6이 나오게 된다!!

결론

역시 손으로 끄적이면 규칙이 곰방 보이네. 덕분에 내 힘으로 풀 수 있었다! 마크다운으로 시그마를 쓰는 방법을 배웠고 시그마 공식을 몸이 기억한다는 사실을 알게 된 건 덤...

번외

이것도 몇 달 후에 다시 직접 풀어보았다.
저렇게 어렵게 하지 않고 그냥 바로
$\displaystyle\sum_{i=1}^{n-2}{(\sum_{j=i+1}^{n-1}{(n-j)})}$ 이렇게 바로 썼다. 수학한 지 너무 오래돼서 이걸 푼다고 굉장히 식을 많이 쓰긴 했는데.. 쨌든 결론은 마찬가지로 n(n-1)(n-1)/6이 나온다! 얘도 전 문제와 마찬가지로 어떻게 해서든 6으로 나누어진다.