[백준] 17213 : 과일 서리

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

17213번: 과일 서리

---

• 각 종류마다 적어도 1개씩은 훔치기 때문에, 이를 제외하고 N 개 그룹에게 M-N 개를 나눠야 하는 문제가 된다.
• 그룹이 1개라면, 몇개가 있든지 간에 무조건 경우의 수는 하나가 된다.
• 그룹이 2개일 경우는, 일단 하나의 그룹이 가져갈 양이 정해지면 나머지 그룹이 가져가는 양은 자동으로 정해진다.
• 3개일 경우 역시, 하나의 그룹의 개수가 정해지면, 나머지 2개의 그룹이 가져갈 양이 자동으로 정해지는데, 이 때 2개의 그룹이 가져갈 수 있는 경우의 수는 위에서 구한 값을 저장해놓는다면 재사용 할 수 있다.
• 따라서 X 개의 그룹들이 가져가는 경우의 수는 X-1 개 그룹이 0개, 1개, 2개, ... , M-N 개 가져가는 경우의 수의 합이 되며, 이를 DP 배열로 저장해서 반복문을 통해 앞에서부터 구해 나간다.
• 다른 사람들의 풀이를 보니, 중복 조합으로 풀 경우 math 패키지의 comb 함수 하나만으로도 문제를 풀 수 있다.

---

N = int(input())
M = int(input())
                                                            # DP[X][Y] 는 X 개의 과일 종류 중 총 Y 개를 뽑는 경우의 수
DP = [[1]*(M-N+1), [1]*(M-N+1)]                             # DP[1][Y] 는 반드시 1.
for X in range(2, N):                                       # DP[X][Y] = sum(a=0~Y, DP[X-1][a])
    DP.append([sum(DP[X-1][:Y+1]) for Y in range(M-N+1)])
print(sum(DP[N-1][:M-N+1]) if N > 1 else 1)                 # DP[N][M-N] 구하기 ,N 이 1 일 경우는 예외처리