hchan-frm 님의 블로그

https://www.acmicpc.net/problem/1309 DP를 이용해서 경우의 수를 따져가며 푼 문제이다. 문제에는 2*N배열의 칸들이 있고, 여기에 사자를 배치할 때 서로 변을 공유하지 않도록 배치하는 경우의 수를 구하는 문제이다. 이때 처음 행의 오른쪽에 사자를 배치하였을 때 나올 수 있는 경우의 수와 처음 행의 왼쪽에 사자를 배치하였을 때 나올 수 있는 경우의 수에 차이가 있을까?오른쪽에 배치하느냐, 왼쪽에 배치하느냐에 따라 그 다음에 배치 가능한 경우의 수는 다르지 않기 때문에 경우의 수 자체는 다르지 않다.즉,(처음 행에 사자를 배치하지 않았을 때 나올 수 있는 경우의 수) + 2*(오른쪽 혹은 왼쪽 칸에 사자를 배치하지 않았을 때 나올 수 있는 경우의 수) = (모든 경우의 수)인..

https://www.acmicpc.net/problem/1149 인접한 집의 색이 같으면 안된다는 규칙을 전제로 모든 집을 Red, Green, Blue 중 하나씩으로 칠할 때 모든 집을 칠하는 비용의 최솟값을 구하는 문제이다. 처음에 칠할 수 있는 경우의 수가 3가지이고, 무엇으로 칠하냐에 따라 다음 집을 칠할 수 있는 경우의 수도 달라지기 때문에 DP를 이용하여 풀 수 있다. 점화식은 다음과 같다.d[i] = i-1번째 집까지의 최소비용 + i번째 집을 칠할 수 있는 색상 중 최소비용top-down 형식으로 재귀함수를 이용하여 해결하였는데, 재귀함수 내부 내용은 다음과 같다.이전 집이 R이면 res = (다음 집이 G일때와 다음 집이 B일때 중 비용이 더 적은 경우가 나오는 것으로 선택) 이전 집이..

https://www.acmicpc.net/problem/11722 가장 큰 증가하는 부분 수열 문제와 굉장히 유사하여 풀이 설명도 거의 비슷하게 했다. 주어진 수열에서 감소하는 일부분들의 길이 중 그 길이가 최대가 될 수 있는 경우를 구해야 하는 문제이다. ※ 예시수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} 이고, 길이는 3이다. 입력받는 수열을 a라고 하고d[i]는 a[i] 이전 숫자들을 보았을 때 a[i]를 포함하여 나올 수 있는 수열 중 가장 긴 수열의 길이로 두었다. 이제 점화식을 생각해내야 하는데, d[i]를 구하기 위해서는 a[0]~a[i-1] 중 a[i]보다 더 크면서(이때 더 큰 숫..

https://www.acmicpc.net/problem/11060 1xN크기의 미로에서 칸에 쓰여진 수 이하 만큼 점프를 할 수 있고, 오른쪽 끝 칸까지 최소 몇번 점프해야 하는지 구하는 문제이다.첫 칸부터 경우의 수를 계산해 나가며 최소 값을 도출해야하며, 이 과정에서 DP를 사용할 수 있다. d[i]를 i번째 칸까지 최소로 올 수 있는 점프 횟수라고 두었다.그 다음 첫번째 칸에서부터 탐색을 시작하는데, 현재의 칸(d[j]라고 가정.)에 적힌 수만큼 앞 칸(d[i]라고 가정.)을 탐색한다.이때 값이 한번도 갱신이 되지 않은 상태(즉, 한번도 탐색을 진행하지 않은 상태)라면d[i] = d[j]+1이고, 이미 탐색이 진행되었던 칸이지만 d[i]가 d[j]+1보다 작으면(= 이전에 저장한 최소 점프 횟수보..

https://www.acmicpc.net/problem/11055 주어진 수열에서 증가하는 일부분들을 합쳤을 때 그 값이 최대가 되는 경우를 구해야 하는 문제이다. ※ 예시 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가하는 부분 수열은 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 이고, 합은 113이다. 나는 이를 DP를 사용하여 풀었다.입력받는 수열을 a라고 하고d[i]는 a[i] 이전 숫자들을 보았을 때 a[i]를 포함하여 나올 수 있는 가장 큰 증가하는 부분 수열의 합으로 두었다. 위의 예시를 활용하여 설명하자면 d[3]은 1, 2, 50을 더한 숫자인 53이 되는 것이다. 이제 점화식을 생각해내야 하는데, d[..

https://www.acmicpc.net/problem/1912 n개의 정수 수열을 받고, 연속된 수를 선택해서 가장 큰 값을 찾아내야 하는 문제이다. 우선, 선택할 수 있는 숫자의 개수는 제한이 없으므로 양수가 연속되어있다면 '무조건' 모두 선택해야한다.이때 문제는 음수가 중간에 있더라도 이를 감안할 수 있는지를 확인하는 것이다. 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 문제에서 제시한 것 처럼 위와같은 수열이 있다고 해보자. 우선 10을 선택해보자.그 다음 숫자는 음수이고, 그 다음 숫자는 양수이다.만약 음수 때문에 10에서 선택을 멈추면 3, 1, 5, 6까지 선택하여 더 큰 값을 만들어내는 상황을 만들지 못한다. 따라서 우선 10과 -4를 선택을 해보고 이 값의 합이 양수..

https://www.acmicpc.net/problem/1699 입력 받은 자연수를 제곱수들의 합으로 표현한 뒤 가장 항의 개수가 적은 경우를 찾아야 하는 문제이다. dp(v) = (자연수 v를 제곱수들의 합으로 표현할 때 그 항의 최소 갯수)로 정의하였다. 이때 dp함수의 매개변수인 cnt는 지금까지 탐색중인 항의 개수를 의미하기에 함수가 재귀적으로 호출이 됨에 따라 cnt값이 늘어난다. dp함수의 반복문에서 때어낼 수 있는 제곱수를 때어내고, 나머지 값을 dp를 통해 최소 항의 개수를 알아내는 방식으로 경우의 수들을 확인한다. C더보기#include int d[100001];int dp(int v, int cnt){ if(v == 0) return cnt; // base if(d[v] >..

https://www.acmicpc.net/problem/1463 어떤 정수(x)를 입력받고 제시된 3가지의 연산을 최소한으로 사용하여 1로 만들 때 사용하는 연산의 횟수를 구하는 문제이다. 제시된 3가지의 연산은 다음과 같이 볼 수 있다.way1: x % 3 == 0 -> 3으로 나눔way2:  x % 2 == 0 -> 2로 나눔way3. 1을 뺌 연산을 사용하는 횟수의 최솟값을 탐색하려면 경우의 수를 탐색해야 한다.이 과정에서 문제의 알고리즘 분류인 DP를 이용할 수 있다. dp[i]가 i를 위의 3가지 연산을 최소한으로 사용하여 1로 만들 때 사용하는 연산의 횟수라고 하면 dp[i] = (dp[i-1]+1, dp[i/2]+1, dp[i/3]+1 중 최솟값) 위와 같이 점화식을 작성해볼 수 있다. 나..