WannaBeDeveloper

4811번: 알약 www.acmicpc.net 이 문제는 N개의 약을 반씩 쪼개서 먹을 때 2N일 동안 약을 먹는 방법의 수를 구하는 문제이다. 즉, 한 개의 약을 쪼갠 뒤 반을 먹는 경우와 반 개의 약을 먹는 경우를 나눠 N개의 약을 2N일에 걸쳐 먹는 방법의 수를 구한다. 문제에서 나와있듯이 이 문제는 약 한 개를 꺼낸 날을 W, 반 개를 꺼낸 날을 H라 했을 때 N개의 W와 N개의 H를 사용해 만들 수 있는 문자열의 개수와 관련이 있다고 할 수 있다. 단, 이러한 문자열을 만들 때 주의해야 하는 점이 있다. 바로 약 한 개를 꺼내 쪼갠 뒤에야 반 개짜리 약을 꺼낼 수 있다는 점이다. 즉, H는 앞에 나온 W의 개수에서 H의 개수를 뺀 결과만큼만 나올 수 있다. 예를 들어 W가 4개 있고 H가 3개 ..

1256번: 사전 www.acmicpc.net 이 문제는 N개의 "a"와 M개의 "z"로 이루어진 문자열만 알파벳 순서대로 수록한 사전에서 K번째 문자열을 찾는 문제이다. 이 문제를 해결하기 앞서, N개의 "a"와 M개의 "z"로 이루어진 서로 다른 문자열의 개수를 생각해 보자. 만약 N개의 "a"와 M개의 "z"가 모두 서로 다른 문자였다면 N+M개의 문자를 이용해 만들 수 있는 문자열의 개수는 (N+M)!일 것이다. 그런데 N개의 "a"와 M개의 "z"는 같은 문자이므로 이들 사이의 순서가 바뀌어도 같은 경우로 간주할 수 있고 따라서 이 경우의 수를 제외해야 한다. N개의 문자를 나열하는 방법의 수는 N!이므로 전체 경우의 수는 (N+M)!/N!M!이다. 이는 N+M개에서 N개를 택하는 조합의 수와 ..

2482번: 색상환 www.acmicpc.net 이 문제는 N개의 색으로 구성된 색상환에서 어떤 인접한 두 색도 동시에 선택하지 않으면서 서로 다른 K개의 색을 선택하는 경우의 수를 구하는 문제이다. 이는 조합을 dynamic programming으로 구하는 방법을 활용한다. 예를 들어 서로 다른 N개의 대상 중 순서없이 K개를 선택하는 경우의 수를 구할 때는 첫 번째 대상을 포함하느냐 포함하지 않느냐에 따라 두 가지 경우로 나누고, 포함하는 경우는 N-1개 중 K개를, 포함하지 않는 경우는 N-1개 중 K-1개를 택하는 경우이므로 두 조합의 경우의 수를 더해서 구할 수 있다. 이 문제도 위와 유사한 형태지만 몇몇 조건이 추가되어 이를 고려해야 한다. 색상환에서 마지막 색을 제외한 상태에서 경우의 수를 ..