16561🐨3의 배수 python

3의 배수를 덧셈으로 나타내는 방법의 가짓수를 구하는 문제이므로, 가장 단순한 경우인 3의 덧셈만으로 3의 배수를 표현하는 방법을 생각해 보자.

예를 들어, 9를 고려해 보자.

3

3

3

여기서 덧셈 기호를 넣을 수 있는 자리는 두 군데이며, 우리는 세 개의 3을 사용해야 하므로 두 개의 덧셈 기호를 반드시 넣어야 한다. 따라서 가능한 방법은 한 가지뿐이다.

이제 12의 경우를 살펴보자.

3

3

3

3

첫 번째 칸에 덧셈 기호를 넣으면 나머지 두 칸 중 하나를 선택할 수 있으며, 첫 번째 칸이 아닌 두 번째 칸에 덧셈을 넣으면 남은 한 칸에만 추가할 수 있다. 따라서 가능한 경우의 수는 $2+1=3$ 가지가 된다.

더 큰 수인 21의 경우를 살펴보고 일반화해 보자.

3

3

3

3

3

3

3

여기서 두 개의 덧셈 기호를 넣어야 한다. 첫 번째 덧셈 기호를 놓을 수 있는 방법이 5가지(빈 칸의 개수 - 1)이며, 그에 따라 두 번째 덧셈 기호를 선택하는 경우의 수는 5, 4, 3, 2, 1가지씩 존재한다.

결국, 빈 칸의 개수만 알면 가능한 경우의 수는

$$(n-1) + (n-2) + \dots + 1$$

으로 구할 수 있다.

여기서 빈 칸의 개수는 3의 개수보다 하나 적으며, 첫 번째 숫자는 그보다 하나 적다.

마지막으로, 1부터 $n$까지의 연속된 자연수의 합을 구하는 공식은 다음과 같다.

$$\frac{n(n-1)}{2}$$

def s():
    l=int(*open(0))//3-1
    print(l*(l-1)>>1)
s()