뚝딱뚝딱

https://www.acmicpc.net/problem/2293

💡 동전 1

✅ 문제 풀이

• 배낭 문제와 접근 방식이 동일하다.
• dp를 이용해 경우의 수를 구해나간다.
• dp[i]=j 는 "n가지 종류의 동전을 이용해서 합이 i원이 되도록 하는 경우의 수가 j개" 라는 뜻이다.
• dp[0]=1이다. 합이 0원이 되는 경우의 수는 아무것도 합하지 않는 경우 1개가 존재하기 때문이다. 따라서 이는 초기값이 된다.
• 만약 동전 종류 중 1원짜리가 있다고 하자. 1원을 가지고 1원을 만드는 경우의 수는 다음과 같다.
  dp[1]=dp[1]+dp[0]
  1원이 되려면, 0원에다가 1원을 더해주면 되니까 0원이 되는 경우의 수를 합해주면 된다. 따라서 1이다.
• 만약 동전 종류 중 3원짜리가 있다고 하자. 3원을 가지고 5원을 만드는 경우의 수는 다음과 같다.
  dp[5]=dp[5]+dp[2]
  5원이 되려면, 2원에다가 3원을 더해주면 되니까 2원이 되는 경우의 수를 합해주면 된다. 
• 즉 dp[i]를 구하려면 i에서 동전 가치 "value[j]"를 빼준 값이 되는 경우에다가 그냥 value[j]를 더하면 i원이 되는 거니까. dp[i-value[j]]를 구하는 것과 동일하다. 즉 i-value[j]원이 되는 경우의 수를 구하는 것과 같다.
• 주의할 점은 어떤 value[j]를 가지고서 i원이 되도록 할 때, i는 value[j]보다 커야 한다는 것이다.
  예를 들어, 3원을 더함으로써 4원을 만들어낼 수 있지만, 3원을 더함으로써 2원을 만들어낼 수는 없다. 이미 3이라는 가치가 2보다 크기때문에, 3원을 더하려면 항상 3원 이상의 큰 가치만을 만들어 낼 수 있다.
• 따라서 다음과 같은 점화식을 따른다.
  dp[i]+=dp[i-value[j]]
  (이때, i>=value[j])
• 위를 모든 동전의 종류에 대해서 반복해주면 된다.
• 최종 답은 dp[k]이다. k원을 만드는 경우의 수 이기 때문이다.   

✏ 코드 전문

#include<iostream>
#include<vector>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, k;
	cin >> n >> k;

	vector<int> value(n);
	for (int i = 0; i < n; i++) {
		cin >> value[i];
	}

	vector<long long> dp(k + 1,0); //출력 범위가 2^31 까지 임에 주의하여 long long으로 선언

	dp[0] = 1;//0원을 만드는 데 필요한 경우의 수 1

	for (int i = 0; i < n; i++) {
		for (int j = value[i]; j <= k; j++) {
			dp[j] += dp[j - value[i]];//j원을 만드는데, value[i]원을 사용하려면 j에서 value[i]를 뺀 값이 필요하고, 이것의 경우의 수를 더해주면 됨.
		}
	}

	cout << dp[k];

	return 0;
}

https://www.acmicpc.net/problem/9251

💡 LCS

✅ 문제 풀이

• 문자열에서 최장 부분 수열의 크기를 찾는 문제
• DP를 이용하여 풀 수 있다.
• dp 배열의 크기는 두 문자열 각각의 크기에 +1 한 만큼으로 행과 열 크기를 배정해준다.
• 행 열 인덱스 0은 모두 0으로 초기화하여 사용할 것이다.
• 그리고 dp 크기만큼 2중 for문을 순회하는데, 각 칸의 값은 해당 칸의 행과 열 알파벳이 동일하면 왼쪽 대각선 위 값에 +1 한 값이고, 다르면 왼쪽과 위에서 오는 값 중 더 큰 값으로 가지게 된다.
  => 이는 표를 그려보면 규칙을 통해 발견할 수 있다.
• 따라서 이를 점화식으로 나타내면 다음과 같다.
  dp[i + 1][j + 1] = dp[i][j] + 1 (행 알파벳=열 알파벳)
  dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j]) (행 알파벳 =/= 열 알파벳)
  
  
• 그리고 dp[r][c] 즉, 가장 오른쪽 아래에 있는 값이 최종 답이 된다.

✏ 코드 전문

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	string str1, str2;

	cin >> str1 >> str2;

	int r = str1.length();
	int c = str2.length();

	vector<vector<int>> dp(r+1, vector<int>(c+1,0));
	
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			int m = max(dp[i][j + 1], dp[i + 1][j]);
			if (str1[i] == str2[j]) {
				dp[i + 1][j + 1] = dp[i][j] + 1;
			}
			else {
				dp[i + 1][j + 1] = m;
			}
		}
	}

	cout << dp[r][c];
	
	return 0;
}

https://www.acmicpc.net/problem/1149

💡 RGB거리

[문제]
RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.1번 집의 색은 2번 집의 색과 같지 않아야 한다.N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.

[입력]
첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.

[출력]
첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.

✅ 문제 풀이

이 문제는 전형적인 DP 문제이다.

집은 R,G,B 세 색상 중 하나로 칠할 수 있는데, 인접한 집끼리는 색이 겹쳐서는 안된다.

그렇게 칠했을 때 모든 집을 칭하는 최소 비용을 구한다.

일단 입력으로 주어지는 각 집당 페인트 비용을 저장하기 위해서 2차원 배열을 사용해보자.

문제에서 주어진 예시를 사용할 것이다.

행은 집의 번호, 열은 각 집의 R,G,B 비용이다.

첫번째 집까지 칠했을 때는 첫번째 집에서 고른 비용이 저장되는 것이고, 두번째 집까지 칠했을 때는 첫번째 집까지 쓰인 비용+두번째 집에서 고른 비용으로 값이 정해진다. 따라서 다음과 같은 점화식을 따른다.

d[i]=d[i-1]+a[i]

그런데, 비용을 최소로 한다고 해서 모든 집에서 가장 작은 비용을 선택해버린다면, 위 예에 따르면 26, 49, 13이 가장 최소가 되어버리고, 모두 빨간색으로만 칠하게 되어버린다. 이는 조건을 위배하게 된다.

따라서 이전 집에서 어떤 색을 칠했는지에 따라서 이번 집에 칠할 수 있는 색이 2개로 추려져야 한다.

그러므로 이전 집을 R로 칠했을때, G로 칠했을때, B로 칠했을때를 모두 계산하고 나서, 최종 집까지 칠했을때 세 값중 최소값이 답이 될 수 있다.

이때 현재 집(i번 집)에 R을 칠하고자 한다면 이전집(i-1)이 G또는 B가 칠해졌어야 하고, 이 둘 중 최소 비용에 현재 집의 R 비용을 더한 값이 d[i][0]이 될 수 있다.

이를 점화식으로 나타내면 다음과 같다.

d[i][0] = min(d[i - 1][1], d[i - 1][2]) + a[i][0]; 
d[i][1] = min(d[i - 1][0], d[i - 1][2]) + a[i][1];
d[i][2] = min(d[i - 1][0], d[i - 1][1]) + a[i][2];

점화식에 따르면 위 표와 같이 정리될 수 있고, 이는 i번째 집까지 칠했을 때의 비용을 나타낸다.

따라서 위 예시의 답은 3번째 집까지 칠했을 때의 비용 96,172,146 중에 최소값인 96이 되는 것이다.

min(min(d[t][0], d[t][1]), d[t][2])

이 식을 통해서 답을 구할 수 있다. (t는 마지막 집의 번호이다)

✏ 코드 전문

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int t;
	cin >> t;

	vector<vector<int>> d(t + 1, vector<int>(3, 0));
	vector<vector<int>> a(t + 1, vector<int>(3, 0));

	for (int i = 1; i <= t; i++) {
		cin >> a[i][0] >> a[i][1] >> a[i][2];
		d[i][0] = min(d[i - 1][1], d[i - 1][2]) + a[i][0];
		d[i][1] = min(d[i - 1][0], d[i - 1][2]) + a[i][1];
		d[i][2] = min(d[i - 1][0], d[i - 1][1]) + a[i][2];
	}

	int answer = min(min(d[t][0], d[t][1]), d[t][2]);

	cout << answer;

	return 0;
}