TOYPRO 해설문 - 그룹화(400점)

1. 개요

경기 프로그래밍 사이트'TOYPRO'의 400점 문제
조를 나누는 해설을 하다.

2. 질문

N명의 학생 중에서 2명을 선택할 때의 그룹 수, 3명이 선택할 때의 그룹 수,,, N인이 선택할 때의 그룹 수를 모두 합칠 때 모두 몇 개의 그룹인지 확인하세요.

구속

2\leq N\leq 100

필요 변수

N

입력 예

N = 3

출력 예

4

3. 해설

이 문제는 두 가지 해결 방법이 있다.두 계산의 최종 값은 모두 같다.

3.1 해법 1 각자의 인원수를 선택할 때 그룹의 총계를 계산한다

여기서 N=3을 고려합니다.

3.1.1 (두 사람이 선택할 때의 조합 수량)

세 사람 중 한 사람을 먼저 선택한다.그리고 두 사람 중에서 한 사람을 선택하세요.
그래서×2=6!나는 누군가가 이렇게 생각할 것이라고 생각한다. 이것은 잘못된 것이다.이 생각에 따라 떠오르는 조합은 아래 그림과 같다.
여기서 눈에 띄는 것은 A, B, B와 A처럼 같은 쌍의 배열 방식을 숫자로 바꾸었다는 것이다.
배열 방식의 영향을 없애기 위해
이 경우 두 가지 배열 방식으로 같은 수량의 두 가지를 나누어야 한다
\frac{3×2}은(는) 3가지가 필요합니다.
조합을 고려할 때 배열 방식의 영향을 고려하세요
이렇게 되면 두 사람이 선택할 때의 단체 수를 구할 수 있다.

3.1.2 (3인 선택 시 조합 수량)

세 사람 중에서 한 사람을 먼저 선택한 다음에 두 사람 중에서 한 사람을 선택하고 마지막에 한 사람을 선택하는 것도 6가지 배열 방식이 있다.×2×1]{6} = 1과 같습니다.
요약하면 N=3의 경우는 4가지다.

3.1.3 해법 1의 총결

위의 설명은 N=3의 경우 N=100의 경우에도 같은 계산을 통해 답을 구할 수 있는 조합수이다.
이 계산을 진행하면 계산량은 2+3+...N=\rac{N(N+1)]{2}-1 때문에
O(N^2)가 됩니다.이것은 이번 제한 하에서 매우 고속이다.
다음은 해답의 예이다.

N = 3
ans = 0
#ans = 答えの数
for i in range(2,N+1):
    p = 1
    q = 1
    #pは分子、qは分母
    for j in range(i):
        p *= N - j
        q *= j + 1
    ans += p // q
print(ans) 

3.2 해법 2를 통해 산출

이번 문제의 유형으로 삼다
N 명 중에 0 명 이상을 뽑은 그룹은 뭐가 있을까요?
이런 문제를 고려해 보아라.
두 가지 옵션으로 나누어 조합을 고려합시다.
다음은 1을 선택하고 0을 선택하지 않은 숫자로 바꿉니다.
문자열의 조합을 고려하여 왼쪽에서 i위(1\leqi\leqN)
정의는 다른 사람의 눈을 선택하는 데 쓰인다.
따라서 다음과 같이 N=3과 같은 이미지가 표시됩니다.

왜냐하면 모든 사람에게 선택하고, 선택하지 않는 조합이 존재하기 때문이다.×2×2=8가지 선택 방법.
이것은 어떤 N에게도 마찬가지다.따라서 N에 대해 2^{N}개의 응답이 있습니다.
2^{N}은 2 N을 곱한 값입니다.예) 2^2 = 4, 2^5=32
여기서부터 이번 문제의 답안은 포함되지 않는다

0명의 선택 방법 (선택하지 않음, 선택하지 않음,...선택하지 않음)의 1종

한 사람의 선택 방법 N줄

2^N-1개가 답입니다.
N은 100까지이기 때문에 값이 매우 커지지만 파이톤은 정수형에 상한선이 없기 때문에 2^{100}을 나타낼 수 있습니다.
따라서 계산량 O(1)로 이 문제를 해결할 수 있다.
다음은 해답의 예이다.

N = 1
ans = 2 ** N - N - 1
#ansは答え
#2 ** Nで2のN乗を計算しています。
print(ans)

4 요약

이번에 두 가지 해법을 소개했는데, 어때요?
나는 조합의 문제는 이렇게 답을 공식으로 바꾸어 계산량을 줄이는 것이라고 생각한다.
여기서 400점 문제의 조를 나누는 해설을 마치겠습니다.