급하게임개발

이 문제는 dp문제이다

#include <iostream>
#include <algorithm>
using namespace std;
//dp[i][j]= 처음부터 i번째 까지의 물건을 살펴보고, 배낭의 용량이 j였을 떄 배낭에 들어간 물건의 가치합의 최댓값
//예를 들어
int dp[101][100001];
int W[101];
int V[101];
int main() {
	//N은 물건의 갯수를 의마한다.
	//K는 버틸수 있는 물건의 무게를 의미한다.
	int N, K;
	cin >> N >> K;
	for (int i = 1; i <= N; i++) {
		cin >> W[i] >> V[i];
	}


	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= K; j++) {
			if (j - W[i] >= 0) {
				//현재 무게의 최댓갑은 이전아이템까지 넣은 단계에서의 최댓값과
				//지금 아이템의 무게를 넣은 물건의 값을 비교하여 더 큰값을 넣는다.
				//i번째 물건을 넣을 지 말지가 중요하다.
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - W[i]]+V[i]);
			}
			else {
				//현재 아이템을 넣었을때 무게가 오바된다면 넣지 않고 이전걸 그대로 가져온다
				dp[i][j] = dp[i - 1][j];
			}
		}
	}
	cout << dp[N][K];
}

코드를 살펴보면 일다 우리는 가지고 있는 첫번째 아이템 부터 차근차근 가방에 넣을 것이다. 차근차근 넣을 때 제한 무게를 초과한다면 그 아이템은 넣지 않는다가 이문제의 핵심이다. 즉 i번째 아이템을 넣은 것과 안 넣은 것의 최댓값을 계속 갱신해주면서 진행하는게 해당 문제의 해결 방법이다. i=1일때 우리는 가방에 이 아이템을 넣을지 말지 결정 한다. dp[0][0]은 어차피 0이다 하지만 무게해당하는 j값이 0이기에 일단 넣지 않는다. 이에 dp[1][6]=13이다 즉 1번아이템을 넣었을 때의 무게는 6이고 13이다라는 의미이다 이제 2번아이템을 넣는다고 가정해보자 2번아이템도 마찬가지로 진행이된다. dp[4][4]의 가치는 일단 8이다 하지만 이제 dp[6]으로 간다면 2번까지 넣어서 6이하의 무게를 만든 가방보다 1번만 넣어서 6이하의 무게를 가진 가방의 가치가 더높으므로 dp[2][6]=13이다. 

자이제 3번아이템까지 넣는다고 가정하자  일단 dp[3][3]=6이다 dp[2][4]=8이고 이에 따라 dp[3][4]=8이다

dp[3][7]의 기준으로 보자 지금 까지는 dp[1][6]의 값이 계속 들어 와서 13이었을 것이다. 하지만 3번 아이템을 넣는다고 가정해보았을 때 dp[2][4]+dp[3][3] 즉 dp[2][4]+V[i]의 값이 기존의 dp[2][7]즉 dp[1][6]의 값이 계속 넣어진 상황 보다 큼으로

갱신된다 

이 문제는 너무 쉽다 dp이긴 한데 점화식으로 풀었다고 하기엔 애매하다 1부터 123을 다 더해서 작으면 다시 더한후 그값이 커지면 그 이후로는 계산을 안하면 되겠다는 생각으로 이 문제를 풀었다 이문제는 생각 보다 매우 쉬웠다 설명할것도 없이 코드를 보면 이해가 될것이다

#include <iostream>
#include<queue>
using namespace std;
int T;
queue <int> n;
int answer[12];
int solution(int start,int answerindex) {
	if (start == answerindex) {
		answer[answerindex]++;
	}
	else if (start > answerindex) {
		return 0;
	}
	else {
		solution(start + 1, answerindex);
		solution(start + 2, answerindex);
		solution(start + 3, answerindex);
	}
	return 0;
}
int main() {
	cin >> T;
	int temp;
	std::ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	for (int i = 1; i <= T; i++) {
		cin >> temp;
		n.push(temp);
	}
	while (!n.empty()) {
		temp = n.front();
		n.pop();
		solution(0, temp);
		cout << answer[temp] << endl;
	}
}

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

DP는 해도해도 실력이 확실히 점화식을 잘세워야 하는 것 같다 이문제의 경우 점화식이 무조건 필요했는데 사실 문제 이해가 잘 안 갔어서 푸는데 4시간 걸렸다......알고리즘 빨리 풀어야하는데  이문제의 경우는 일단 예시로 나온

을 기준으로 하면 동전의 갯수 만큼의 경우의 수를 생각 해주어야 했다

맨처음 첫번째 동전인 1원만으로 1원 부터 10원 까지 만들 수 있는 경우의 수를 dp 에 채워 준다 그 후

2원 부분의 행을 채워 줘야한다 2원 부분의 행은 무조건 해당 단계에서 2원만을 사용해서 그 해당 수를 만들어 주는 경우의 수다 이부분에서는 5원에 대한 생각은 해주지 않습니다 2원의 행은 2원과 1원 부분만을 이용해서 그 해당 원수를 만드는 것 입니다

이에 이렇게 쭉 구하면서 5원 부분까지 가면 10월을 만들 때 딱 5원을 추가하여 10원을 만드는 경우의 수는 5원으로 5원을 만든 경우의수와 1원과 2원으로 만든 5원의 경우의 수와 1원으로만 만든 5원의 경우의 수를 더하여 4가지가 나온다 이렇게 생각을 하게 되면 이문제의 dp를 추정 할 수 있습니다 하지만 위에거를 그대로 사용하여 2차원 배열을 사용하게 되면 4mb를 초과하는 사태가 발생하여 틀렸습니다가 생겼습니다 이에 우리는 위에 식을 이용해 점화식을 더간단한 점화식을 만들어야합니다.

점화식을 세울때 우리가 봐야할 부분은 합계입니다  2원에서의 합계를 보시지요 자 기존에 1원에서 만 만들었던 값에서 자기자신을 뺀 부분에서의 값을 더해줌으로서 지금 원을 만드는데 2원을 넣었다고 가정했을 때의 경우의 수를 더해주게 됩니다.

각 2원의 행을 예시로 봅시다 2원의 행은 지금 계속 표를 보면 0원에서 2원

dp[2] += dp [0]   2

dp[3] += dp [1]   2

dp[4] += dp [2]   3

즉 dp[2] 의경우 1원으로 만든 경우의 수 + 0원의 경우의 수가 됩니다 이유는 0원에서 2원을 고름으로서 2원을 만들 것이기 때문입니다 이에

dp 배열의 합계 부분들은 이런식으로 값이 바뀌게 됩니다.

즉 먼저 하나의 코인으로 해당 값을 만든 다고 가정하고 그 경우의 수에서 나의 동전값을 뺏을 때의 경우의 수를 더해줘야 합니다 

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

이 문제는 내가 지금 까지 DP배열을 1차원 배열로 만드는데 익숙 해져서 그런지 2차원 배열로 설정 하는 것을 생각을 못해서 어려운 문제 였다. 이 문제의 경우 나는 이렇게 생각 해주었다.

일단 나는 이문제를 1번 아이템 부터 4번아이템을 넣어준다고 가졍하였다 이문제에서 0은 어떠한 아이템도 안 넣었다고 생각해서 0이자 무게가 0이라고 생각을 했다 이렇게 생각하지 않으면 너무 헷갈렸다 그래서 1번을 넣었을 때 무게가 6이고 7인 경우에는 1을 넣었기 때문에 1의 무게인 13을 넣었다. 1을 넣었을 때 무게가 1,2,3,4 일 수는 없으니 1을 넣지 않았다는 표시이자 안 넣었고 무게도 0이니 0으로 한다. 2번아이템을 넣었을 때 도 마찬가지 무게가 1,2,일 때는 2번을 넣었을 때

무게가 4로 초과되니 0으로 표시한다 그후 무게가 4랑 5일때는 

나의 이전 단계인 1을 넣었을 때의 무게들 중 나를 안넣었다고 가정한 무게 + 나의 무게를 했을 때와 이전단계의 무게들과 비교하여 더큰 값을 넣어준다. 이것을  dp로 표현 하면

dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - W[i]] + V[i]); 

예시로 dp[2][6]은 dp[1][2]+v[2] 과 dp[1][6]일 때를 비교한다 이 의미는 1을 먼저 넣을 안넣을 지 결정하는 상태에서 무게가 2일때+나의 더했을 때의 가치와 1을 넣을 안넣을지 결정했을 무게가 6인 경우를 비교하여 더 큰 값을 선택한다.

쉽게 설명하자면

1을 넣을지 말지 결정했을 때  특정 무게를 맞춘다고 가정했을 때 나의 무게를 더해서 그 무게를 맞춘다고 가정한 값과 이전 단계에서 그 무게를 달성했을 때의 값을 비교하여 큰값을 선택해 주는것이다.

#include <iostream>
#include <algorithm>
using namespace std;
long long dp[101][100001];//가방 물건의 번호,내가방의 무게
int W[101];
int V[101];
int main() {
	int maxItemNum;
	int maxItemWeight;
	cin >> maxItemNum >> maxItemWeight;

	for(int i=1; i<=maxItemNum; i++){
		cin >> W[i] >> V[i];
	}

	for (int i = 1; i <= maxItemNum; i++) {
		for (int j = 1; j <= maxItemWeight; j++) {
			if (j - W[i]>=0) {
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - W[i]] + V[i]);
			}
			else {
				dp[i][j] = dp[i - 1][j];
			}
		}
	}
	cout << dp[maxItemNum][maxItemWeight];
}

그래서 이러한 점화식으로 이문제를 풀면 전체 식이 이렇게 된다. 1차원으로 dp를 세우는 거 뿐만 아니라 다차원의dp 도 세우는 방법을 연습해야 할거 같다.

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

이문제의 거의 다풀어놓고 위에 배열크기를 잘못 설정해서 계속 틀렸다. 진짜 알고리즘 문제 풀면서 항상 느끼는 거지만 배열의 크기에서 오타나면 항상 틀리는 거같다 이문제의 경우 총 2가지의 케이스를 생각해줄 수 있다

자 40을 예시로 들면 자기이전에 변을 맞대지 않는애들 고르면 자동적으로  2번째거 이전 위에거가 선택 된다

2번째거 이전에 반대쪽애를 선택해주면 3번째거 이전에 위에거 가 선택 된다 이렇게 짠이유는 이전꺼 아래거와 2번째전거 위에거 더한게 2번째거 전에 거와 3번째전에거의 위에거의 합이 더 클 수 있기 때문이다 이에 이 문제의 점화식은

dp[l][0]=max(dp[l - 1][1] + card[l][0], dp[l - 2][1] + card[l][0])

이렇게 맨마지막에 위에거를 선택했을 때와

dp[l][1]=max(dp[l - 1][0] + card[l][1], dp[l - 2][0] + card[l][1])

이렇게 맨마지막에 아래거를 선택 했을 때 2개가 존재한다

#include <iostream>
#include <algorithm>
int dp[100001][2];
int card[100001][2];
using namespace std;
int main() {
	int T;//테스트케이스
	int n;//해당하는 스티커의 점수
	cin >> T;
	for (int i = 0; i < T; i++) {
		cin >> n;
		for (int j = 0; j < 2; j++) {
			for (int k = 1; k <= n; k++) {
				cin >> card[k][j];
			}
		}
               
		dp[1][0] = card[1][0];
		dp[1][1] = card[1][1];
		for (int l = 2; l <= n; l++) {
			dp[l][0] = max(dp[l - 1][1] + card[l][0], dp[l - 2][1] + card[l][0]);
			dp[l][1] = max(dp[l - 1][0] + card[l][1], dp[l - 2][0] + card[l][1]);
		}
		cout << max(dp[n][0], dp[n][1])<<'\n';
	}
}

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

이 문제의 경우 여러방면으로 풀려고 시도 했으나 결국 또 점화식을 계속 이상하게 세워서 빨리 풀지 못했다

이 문제는 점화식만 처음에 방향을 잘잡고 풀었으면 빨리 풀렸을 거 같은 문제였다 일단 이문제는

카드를 1장만 산다고 생각해서 카드 개수를 늘려가면서 점화식을 세우는게 효율적이 었던거 같다.

이 문제의 dp배열은 해당 인덱스 장만큼의 카드를 살때의 최댓값을 나타낸다.

일단 dp배열을 초기화 할때 각배열에 그 장만큼의 카드를 살 때의 가격을 넣어준다

일단 카드 1장을 살 때는 경우의 수가 카드 1장짜리를 사는 경우의 수밖에 없으니  팩의 최댓값을 나타내는 dp[1]의 값이 밑에 처럼된다

dp[1]= 1장 짜리 카드팩의 가격

이런식으로 넣는다

dp[2]= 1장을 샀을 때의 최댓값 +1장을 샀을 때의 최댓값 와 2팩짜리를 샀을 때 중 큰 값을 골라준다

dp[3]= 2장을 샀을때의 최댓값 + 1장 짜리 샀을때의 최댓값과  3팩짜리를 샀을 때의 최댓값을 비교해서 큰값을 골라준다

dp[4] 부터는 경우의  수가 많아진다 

dp[4]= 1장을 삿을때의 최댓값사고 3장을 샀을 떄의 최댓값, 2장을 샀을 때의 최댓값 + 2장을 샀을때의 최댓값 4팩짜리를 샀을 때의 값중 최댓값을 골라서 넣어준다 이것을 간단히 식으로 나타내면

dp[1]=dp[1];

dp[2]=max(dp[1]+dp[1],dp[2])

dp[3]=max(dp[1]+dp[2],dp[2]+dp[1],dp[3])

dp[4]=max(dp[1]+dp[3],dp[2]+dp[2],dp[3]+dp[1],dp[4]) 

이런식으로 규칙성이 발생해서 점화식을 만들수 있다

#include <iostream>
#include <algorithm>
using namespace std;
int dp[1001];
int main() {
	int N;
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> dp[i];
	}
	for (int i = 2; i <= N/2; i++) {
		for (int j = 1; j < i; j++) {
			dp[i] = max(dp[i], dp[j] + dp[i - j]);
		}
	}
	cout << dp[N];
}

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

이건 개념은 쉬웠다 근데 계속 틀렸습니다 나오길 래 코드를 뜯어봤더니 int의 범위를 초과해서 갑자기 값이 음수로 바뀌는 사태가 발생해서 100정도를 넣으면 값이 이상하게 나왔다 그래서 이코드는 중간중간에 값에다가 모듈러 연산을 해서 저장해주는 게 해결책이었다.

자 일단 첫번째 자리수 즉 수의 맨앞에 나오는 수는 0이 나오면 안된다 그렇기에 첫번째 자릿수가 0

이 될 경우의 수 는 0이다 그리고 나머지는 첫번째 자리에 나오는게 가능하니 1이다

2번째자릿수의 0은 이전자리에서 1에서 오는 방법밖에 없다 9도 마찬가지다 9로가는 방법은

이전자리의 수에서 8에서 밖에 오는 방법밖에 없다

그래서 0일때의 점화식은

dp[i][j] = dp[i - 1][j + 1];

9일때의 점화식은

dp[i][j] = dp[i - 1][j - 1];

이렇게 된다

#include <iostream>
using namespace std;
long long dp[101][101];
int main() {
	long long N;
	long long sum = 0;
	cin >> N;
	dp[1][0] = 0;
	for (int i = 1; i <= 9; i++) {
		dp[1][i] = 1;
	}
	
	for (int i = 2; i <= N; i++) {
		for (int j = 0; j <= 9; j++) {
			if (j == 0) {
				dp[i][j] = dp[i - 1][j + 1];
			}
			else if (j == 9) {
				dp[i][j] = dp[i - 1][j - 1];
			}
			else
				dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1];
				
			dp[i][j] = dp[i][j] % 1000000000;
		}

	}

	for (int i = 0; i <= 9; i++) {
		sum += dp[N][i];
		sum %= 1000000000;
	}
	cout << sum;
}

이 두 부분을 제외하고는 이전자리의 수에서 나보다 하나 크거나 하나 작은 곳에서 부터 올수 있으니

2개의 경우 의 수를 합쳐준다 즉

3번째 자리에 3은 2번째자리에 2와 4로부터 오는것이니 [2][4]+[2][2]를 하면 된다

그래서 이부분의 점화식은

dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1];

이렇게 된다. 하지만 숫자가 너무 커지게 되니 이 연산이 끝나고 나면 모듈러 연산을 해주면 좋다

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

dp문제는 풀 때 마다 점화식이 중요하다고 생각되어진다 역시 이번 문제도 점화식인데

이번문제의 경우 기존에 올렸던과는 다르게 3개의 후보중 하나를 뽑는 방식으로 생각해주어야 한다

그이유는 이번 문제에서 핵심적인 내용이 연속으로 3개의 포도주를 못마신다는 거였으니  그거를 이용해서 풀어야 한다

1.O O X O

2.O X O O

3.X O O X

이문제는 위에처럼 3가지 경우의 수가 존재 한다 즉 N번째 와인이 존재한다고 가정했을때 N번째 와인을 마신다고 가정했을때 첫번째로 마시냐 두번째로 마시냐 혹은 안마시냐 이렇게 3개의 경우의 수가 존대 한다. 이를 점화식으로 나타내면

1은 dp[j-2]+arr[j];

2는 dp[j-3]+arr[j-1]+arr[j]

3은 dp[j-1]

이다 1은 j번째 포도주를 먹기로 가정했기 때문에 내이전은 못마시고 나보다 2개전에 있는 애를 마실 수 있다

2는 나도 마시고 내이전도 마신다고 가정한것이다 

마지막은 나를 안마셨기 때문에 나의 이전까지의 최대값만 필요하다 어차피 이렇게 우리가 3개의 식으로 나눴을 경우 3잔을 연속으로 마시는 경우의 수는 발생하지 않는다

#include <iostream>
#include <algorithm>
using namespace std;
int dp[10001];
int arr[10001];
int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
	}
	dp[1] = arr[1];
	dp[2] = arr[1] + arr[2];

	for (int j = 3; j <= n + 1; j++) {
		dp[j] = dp[j - 1];
		dp[j] = max(dp[j], dp[j - 2] + arr[j]);
		dp[j] = max(dp[j], dp[j - 3] + arr[j - 1] + arr[j]);

	}
	cout << dp[n] << endl;
}