[고등부] 2023 KOI 대비 모의고사 (4월 1주차)

수열 A는 {1, 2, ..., N-1, N}와 같이 1부터 N까지의 수로 이루어져있다.

해당 수열 A를 반으로 나누었을 때, 나누어진 두 부분수열의 합이 같은 경우를 구하고 싶다.

예를 들어 N이 3이라면, 수열은 ​{1, 2, 3} 이며, 이를 두 개의 부분​수열로 나눠 합이 같은 경우는 아래와 같이 한 가지 경우만이 존재한다.

- {3} / {1,2}

수열 안의 숫자의 순서가 다른 경우는 같은 경우로 취급한다.

만약 N이 7이라면 수열은 {1, 2, 3, 4, 5, 6, 7}으로 아래와 같이 네 가지 경우의 수가 나온다 :

- {1,6,7} / {2,3,4,5}

- {2,5,7} / {1,3,4,6}

- {3,4,7} / {1,2,5,6}

- {1,2,4,7} / {3,5,6}

N이 주어졌을 때, 수열 A를 두 개의 부분​수열로 나누었을 때, 두 부분​수열의 합이 같은 경우의 수를 출력하시오.