백준 4811번 : 알약 in Python
이 문제는 N개의 약을 반씩 쪼개서 먹을 때 2N일 동안 약을 먹는 방법의 수를 구하는 문제이다. 즉, 한 개의 약을 쪼갠 뒤 반을 먹는 경우와 반 개의 약을 먹는 경우를 나눠 N개의 약을 2N일에 걸쳐 먹는 방법의 수를 구한다.
문제에서 나와있듯이 이 문제는 약 한 개를 꺼낸 날을 W, 반 개를 꺼낸 날을 H라 했을 때 N개의 W와 N개의 H를 사용해 만들 수 있는 문자열의 개수와 관련이 있다고 할 수 있다. 단, 이러한 문자열을 만들 때 주의해야 하는 점이 있다. 바로 약 한 개를 꺼내 쪼갠 뒤에야 반 개짜리 약을 꺼낼 수 있다는 점이다. 즉, H는 앞에 나온 W의 개수에서 H의 개수를 뺀 결과만큼만 나올 수 있다. 예를 들어 W가 4개 있고 H가 3개 있는 경우에는 앞으로 H는 한 번밖에 나올 수 없다.
이 조건을 고려해서 조합의 수를 찾아야 한다. 이를 위해 조합 계산을 위한 (2N+1)*(N+1) 행렬 combination을 만들고, 초기값으로 combination[i][0] ( 1<=i<=n ) 을 1로 둔다. 그리고 i가 2일 때부터 2N일 때까지, j가 1일 때부터 min(i//2, N)일 때까지 조합 공식을 사용해 combination[i][j]를 계산한다. (즉, combination[i][j] = combination[i-1][j] + combination[i-1][j-1]을 사용) 이때 j가 min(i//2, N)일 때까지 하는 이유는 j가 여기서는 약 반 개를 먹는 일수를 의미하는데, 이 일수는 절대 전체 일수의 절반을 넘을 수 없기 때문이다. 또한 이렇게 함으로써 계산 중간에 약 반 개를 먹는 일수가 전체 일수의 절반을 넘는 경우에 해당하는 entry가 항상 0이 되므로 조합 공식 적용 중에 문제가 발생하지 않는다. 이를 모두 마친 뒤에는 2N개의 약을 모두 먹는 경우의 수인 combination[2N][N]을 출력하면 된다.
이를 코드로 구현하면 다음과 같다.
while True:
N = int(input())
# 입력의 마지막 줄일 경우 while loop을 빠져나온다.
if N == 0:
break
# 조합의 수를 구하기 위한 행렬
combination = [[0]*(N+1) for _ in range(2*N+1)]
# 초기값 설정
for i in range(1, N+1):
combination[i][0] = 1
# 조합 공식을 이용해 조합의 수를 계산한다. 단, j의 최댓값을 min(i//2, N)으로 해
# 약을 반 개 먹는 일수가 전체 일수의 절반이 넘어가지 않도록 한다.
for i in range(2, 2*N+1):
for j in range(1, min(i//2+1, N+1)):
combination[i][j] = combination[i-1][j] + combination[i-1][j-1]
print(combination[2*N][N])