문제 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 풀이 조합 공식을 이용하면 된다. 동쪽이 서쪽에 비해 더 많거나 같은 사이트를 가지고 있기 때문에 동쪽 M개에서 서쪽 N개 중 하나를 고르는 조합인 $_{M}C_{N}$을 구하면 된다. $_{M}C_{N}$을 구하는 조합 공식은 아래와 같다. 위의 공식으로 팩토리얼 값을 계산하여 풀이할 수도 있지만, 이 문제는 조합의 성질을 이용해 점화식을 만들고 dp로 풀이할 수 있다. 위의 두 가지 성질을 이용해 점화식을 세울 수 있고, 이 성질들은 파스칼 삼각형으로 ..

문제 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 풀이 이 문제는 3가지 dp배열을 만들고 각각 현재 줄에서 R, G, B를 선택하는 경우를 저장해주는 것으로 해결할 수 있다. 예를 들어 N번 줄에서 R를 선택할 경우에는 N - 1번 줄에서는 G나 B를 선택해야하고 둘 중에서 더 적은 비용의 숫자를 골라 현재 줄의 R을 선택하는 비용과 합쳐준 비용을 dpR배열에 저장해준다. R G B 26 40 83 49 60 57 13 89 99 이 경우에서 dp배열들은 dpR[0] = 26, dp..

문제 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 풀이 문제를 보고 일단 타일의 모습을 그려보기로 했다. n의 타일은 n - 1 의 타일에 세로 타일이 하나씩 추가된 모습과, n - 2의 타일에 가로 타일 두개씩 추가된 모습이다, 이를 점화식으로 나타내면 dp[n] = dp[n - 1] + dp[n - 2] 이다. 이 점화식을 이용해 문제를 해결하면 된다. 코드 fun main() { val br = System.`in`.bufferedReader() val bw = System.out.bufferedWriter() val mo..

문제 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 풀이 문제에서 주어진 코드대로 피보나치 수열을 재귀함수로 구현하고, 0과 1을 세는 방법으로 문제를 풀면 시간초과가 발생한다. 대신 DP를 이용해 피보나치 수열을 풀면 된다. 피보나치 수란 한 단계 전의 숫자와 두 단계 전의 숫자를 합한 수의 수열이다. 예를 들어 1, 1, 2, 3, 5, 8 ... 등이 피보나치 수이다. 피보나치 수를 점화식으로 나타내면 dp[n] = dp[n - 1] + dp[n - 2]이다. 이 점화식에서 dp[n - 1] = dp[n - 2] + dp[n - 3] 이고 dp[n - 2] = dp[n - 3] + dp[n - 4]..

문제 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 풀이 N을 만들기 위한 3가지 방법은 다음과 같다. 1. N가 3으로 나누어 떨어지면, 3으로 나눈다. 2. N가 2로 나누어 떨어지면, 2로 나눈다. 3. 1을 뺀다. 이를 식으로 표현하면, 1. dp[n] = dp[n/3] + 1 2. dp[n] = dp[n/2] + 1 3. dp[n] = dp[n-1] + 1 이고, 3나누기 -> 2나누기 -> 1빼기의 차례대로 연산을 사용하는 횟수가 적어질 것이다. 따라서 우선 dp[n]을 dp[n-1] + 1인 경우로 저장하고, 2의 배수이면 dp[n/2] + 1, 3의 배수이면 dp[n/3] + 1 으로 계산해준다. 코드 im..