문제 1965번: 상자넣기 정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 www.acmicpc.net 풀이 이 문제는 최장 증가 수열(LIS, Longest Increasing Subsequence)을 구하는 문제로, 동적 프로그래밍(DP)을 활용하여 해결할 수 있다. 입력받은 배열에서 반복문을 통해 현재 위치에서 앞의 원소들의 값과 비교하며 값을 갱신하면 된다. 만약 앞의 원소가 현재 원소보다 작다면 상자에 넣을 수 있으므로 해당 위치의 값 + 1을 현재 위치의 DP값과 비교하여 갱신해주면 된다. [1, 6, 1, 7, 5, 8]에 대해 LIS을 구하는 알고리즘을..

문제 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 풀이 DP를 활용하여 해결할 수 있으며 주어진 예제 입력을 dp 배열로 메모이제이션한다면 다음과 같다. arr 10 20 10 30 20 50 dp 1 2 1 3 2 4 10은 10보다 작은 값이 없기 때문에 길이가 1인 수열이 되고, 50은 10, 20, 30, 50으로 길이가 4인 수열이 된다. 이를 DP로 해결하기 위한 반복문을 만들어보자. 입력 받은 배열을 순회하며 각 원소..

문제 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net 풀이 문제는 시작점부터 도착점까지 도달 가능한 경로 수를 구하는 것이다. 처음엔 DFS로 시도했지만 시간초과가 발생하여 반복문과 DP를 활용한 풀이를 하였다. 시작점인 dp[0][0]에 1을 할당하고, 반복문을 통해 각 위치까지의 도달 가능한 경로 수를 구한다. dp[i][j]가 0인 배열은 처리하지 않고 넘어가도록 하며 0이 아닌 경우에는 오른쪽과 아래 방향으로 map[i][j]만큼 이동 한 후, 그 지점의 dp 배열에 현재 위치 경로 수를 더..

문제 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 풀이 먼저 타일들을 나열해 보자. N = 1 / 1 N = 2 / 00, 11 N = 3 / 001, 111, 100 N = 4 / 0000, 1100, 0011, 1111, 1001 N = 5 / 00001, 11001, 00111, 11111, 10011, 00100, 11100, 10000 타일의 가짓수는 1, 2, 3, 5, 8개로 증가하며 피보나치 수열의 패턴을 보이고 있다. 따라서 dp[N] = dp[N - 1] + dp[N - 2]의 점화식을 사용하..

문제 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 풀이 점화식을 만들기 위해 문제에서 주어진 규칙을 보면, 1. 계단은 한번에 한 계단, 두 계단씩 오를 수 있다. 2. 연속된 3개의 계단을 밟으면 안된다. 이 규칙에서 현재 계단 N을 밟기 위한 방법으로는 N - 2에서 N까지 두 계단 이동한 경우와 N - 3에서 N - 1까지 두 계단 이동하고 N - 1에서 N까지 한 계단 이동한 경우로 2가지만 가능하다. 연속해서 3개의 계단을 밟는 것이 불가능하기 때문에 위의 두 가지 방법이 전부가 된다. 그렇다면 현재 계단에서..