RGB 거리 (실 1) : https://www.acmicpc.net/problem/1149 N개의 집이 주어지고 각 집을 세 가지 색깔로 칠할 시, (단, 색깔은 이전 집을 칠한 색깔과 동일하면 안된다) 모든 집을 칠하는 비용의 최솟값을 구하는 문제. 1. 문제 분석 모든 집을 칠하는 최솟값을 구하는 문제이니, 최적화 문제. 1. 그리디한 접근이 가능한가? 각 선택에 대하여 최솟값만을 선택한다고 했을 시, 정답이 된다는 보장이 없다. 반례도 충분하다. 따라서, 칠하는 경우의 수와 최솟값를 하나하나 계산해봐야 한다. 2. 최적 부분 구조인가? yes. 이전 선택에 관계없이, 각 부분 문제를 최적으로 풀었을 시 전체의 해답이 나옴. DP 식을 도출해보면 알 수 있음. 집 칠하는 비용의 최솟값을 리턴하는 함..

1, 2, 3 더하기 3 (실 2) : https://www.acmicpc.net/problem/15988 재귀문제인 1, 2, 3 더하기 문제(https://sanghoonly.tistory.com/21)를, DP를 활용하여 메모이제이션을 적용한 문제 및 코드이다. 이전 문제는 n의 범위가 작아서 단순 재귀 호출로 충분히 풀 수 있었지만, 이 문제의 경우는 n이 1000000이하로 급격하게 커지니 메모이제이션은 필수이다. 또한 n이 커짐에 따라 정답도 급격하게 증가하니, 정수 범위에 조심할 것!! #include #include #include using namespace std; long long cache[1000001]; long long recur(long long n) { long long &..

가장 긴 증가하는 부분 수열 (실 2) : https://www.acmicpc.net/problem/11053 가장 긴 증가하는 부분 수열 4 (골 4) :https://www.acmicpc.net/problem/14002 DP에 관하여 워낙 유명한 문제. 여기서는 LIS를 실제로 출력하는 코드를 위주로 살펴본다. 1. (일반적인) 최대 증가 부분 수열의 길이 반환 #include #include #include using namespace std; int N, A[1001], cache[1001]; int lis(int start) { int &ret = cache[start + 1]; if (ret != -1) return ret; ret = 1; for (int i = start + 1; N > i..

제곱수의 합 (실 3) : https://www.acmicpc.net/problem/1699 주어진 자연수 N을 이렇게 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 구하는 문제. 난이도는 실버 3인데 골드5인 합분해보다 어려웠고, 헤맸다. 1. 문제 분석 및 접근 최적화문제. 최적 부분 구조를 가지고 있다. 왜냐하면 이전 선택과 현재 선택은 독립적이며, 이전 선택에 관계없이 현재 선택에서 선택의 최솟값만을 도출해내면 되기 때문이다. 또한 그리디하게, 매번 가장 큰 제곱수를 선택하는 방법을 생각했는데, 바로 반례가 나오더라. 예로 들어 n = 32인 경우, 그리디한 접근 : 25 + 4 + 1 + 1 + 1 = 5개 정답 : 16 + 16 = 2개 따라서, 만들어질 수 있는 모든 경우의 수를 살펴 보..

합분해(골 5) : https://www.acmicpc.net/problem/2225 0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 문제. 즉, n = 3, k = 2가 주어지면, (0, 3) (1, 2) (2, 1) (3, 0)의 네 가지 경우의 수를 구할 수 있음. 1. 문제 분석 경우의 수를 모두 구하는 문제니, 최적화 문제는 아님. for문 돌면서 k가 1씩 감소하면서 재귀 호출을 하면 될 것 같음! 2. 완전 탐색 구현 #include using namespace std; int disassemble(int n, int k) { if (k == 0) { if (n) return 0; return 1; } int cnt = 0; for (int num = 0; n + ..

https://www.acmicpc.net/problem/1463 1. 문제 분석 연산을 사용하는 횟수의 최솟값을 출력. 즉 최적화 문제. 계속 3 또는 2로 나누면서 숫자를 더 많이 줄여나가면서 끝에 값을 도출하는 그리디한 접근은 불가능함. 문제에서 주어진 10의 예에서 볼 수 있듯이, 만약 그리디한 방식으로 접근할 경우 10 -> 5 -> 4 -> 2-> 1 의 총 네 번이 필요하지만, 최솟값의 경우 10 -> 9 -> 3 -> 1 로 세 번만에 만들 수 있음. 따라서, 모든 경우의 수를 살펴보는 완전 탐색을 채택. 2. 접근 아이디어 연산을 사용하여 최솟값을 도출하는 함수를 oper()라고 했을 때, 다음과 같이 수식화 할 수 있음. oper(n) = min(oper(n / 3), oper(n / ..

https://www.acmicpc.net/problem/11726 타일 채우기 문제. 타일 채우기 문제들은, DP를 연습할 때 가장 많이 접하는 유형이기도 하다. 1. 문제 분석 가. 문제 분류 타일의 채우는 전체의 경우의 수를 구해야하므로, 완전 탐색 문제. 최적화 문제는 아님. 단순히 전체 경우의 수를 구해 반환하면 됨. 나. 접근 아이디어 2 x n 크기의 직사각형을 채울 경우의 수는 다음과 같이 생각해 볼 수 있음. 2 x n 크기를 채울 경우의 수 = (세로 직사각형 하나 + 2 x n - 1 크기를 채울 경우의 수) + (가로 직사각형 두개 + 2 x n - 2 크기를 채울 경우의 수) 즉, 2 x n 크기를 채울 경우의 수를 리턴하는 함수를 fill(n)이라 했을 시, f(n) = f(n ..