백준 14568번 - 2017 연세대학교 프로그래밍 경시대회

백준 14568번 - 2017 연세대학교 프로그래밍 경시대회

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

문제

• 2015, 2016년에 이어 2017년에도 연세대학교 교내 프로그래밍 경시대회가 열린다.

• 택희, 영훈이, 남규는 열심히 문제를 만들었고, 이에 대한 보상으로 과사로부터 사탕 N개를 받았다.

• N개의 사탕을 적절히 나눠 가지기 위해 토론한 결과, 아래와 같은 방식으로 사탕을 나누기로 결정하였다.

  • 남는 사탕은 없어야 한다.

  • 남규는 영훈이보다 2개 이상 많은 사탕을 가져야 한다.

  • 셋 중 사탕을 0개 받는 사람은 없어야 한다.

  • 택희가 받는 사탕의 수는 홀수개가 되어서는 안 된다.

• 이제 사탕을 적절히 나누어 집에 돌아가던 중, 택희는 위와 같은 규칙을 만족하도록 세 명에게 사탕을 나누어 주는 방법의 수가 궁금해졌다.

• 사탕의 개수 N이 주어지면, 사탕을 세 사람에게 분배하는 서로 다른 경우의 수를 세 보자.

입력

• 첫째 줄에 사탕의 총 개수 N이 주어진다. (1 ≤ N ≤ 100)

출력

• 규칙에 맞게 사탕을 분배하는 경우의 수를 출력한다.

• 택희, 영훈이, 남규가 받은 사탕의 수를 각각 A, B, C개라고 할 때, 서로 다른 (A, B, C) 순서쌍의 수를 세면 된다.

• 만일 규칙에 맞게 사탕을 분배하는 방법이 없다면 0을 출력한다.

접근

1) N이 9이고 택희가 2개를 가져갈 때

• 남규가 영훈이보다 더 가져가야할 사탕 2개를 미리 빼둔다.

• N(9)에서 택희의 사탕 2개와 미리빼둔 2개를 제외한 나머지 5개를 2명이 가져가는 조합을 계산한다.

• (1, 4), (2, 3) 두 가지 방법이 있다.

• (1, 4) : 택희 2개, 남규 6개, 영훈 1개

• (2, 3) : 택희 2개, 남규 5개, 영훈 2개

2) N이 10이고 택희가 2개를 가져갈 때

• 같은 방법으로 6개를 2명이 나눠가지는 방법을 계산한다.

• (1, 5), (2, 4), (3, 3) 세 가지 방법이 있다.

• (1, 5) : 택희 2개, 남규 7개, 영훈 1개

• (2, 4) : 택희 2개, 남규 6개, 영훈 2개

• (3, 3) : 택희 2개, 남규 5개, 영훈 3개

3) N개에서 택희가 i개를 가져갈 때

• N-i-2개를 2명이 나눠가지는 방법을 계산한다.

• 위의 예를 바탕으로 일반화 하면 경우의 수는 (N-i-2)/2 개이다.

따라서 택희가 가져갈 i개를 2부터 2씩 늘리면서 나머지 경우의 수를 더해가면 된다.

Python Code

n = int(input())
s = 0
for i in range(2, n-1, 2):
    s += (n-i-2)//2
print(s)