다이나믹 프로그래밍[Dynamic Programming] 문제풀이-2 (10문제)

11048 이동하기 https://www.acmicpc.net/problem/11048

문제의 특징
1. 시작-> 도착
2. 이동방향
3. 양의 정수

이동할수록 문제의 크기가 작아진다.
위나, 왼쪽으로 이동 못하므로
-> 항상 문제가 작아지므로 다이나믹 프로그래밍이라고 알 수 있다.

풀이 1

O(NM) = NxMx1
D[i][j] = (i, j)로 이동할 때 가져올 수 있는 최대 사탕 개수
D[i][j] = Max(D[i-1][j-1], D[i][j-1], D[i-1][j]) + maps[i][j];

for(int y=1; y<=h; ++y) {
	for(int x=1; x<= w; ++x) {
		d[y][x] = max3(d[y-1][x-1], d[y-1][x], d[y][x-1]) + maps[y][x];
	} // max({num1, num2, num3}); or max(max(a, b), c));
}
//범위 검사가 필요 없었음. maps[y][0], maps[0][x] 는 0으로 초기화 되어 있으므로.

풀이 2
현재 d[i][j]까지 값을 채웠고 다음 3가지 방법을 채우는 방법 (1번과 순서가 다름)

D[i][j+1] = D[i][j] + maps[i][j+1];
 = max(D[i][j+1]);

for(int y=1; y<=h; ++y) {
	for(int x=1; x<= w; ++x) {
		if(d[y][x+1] < d[y][x] + maps[y][x+1]) 
			 d[y][x+1] = d[y][x] + maps[y][x+1];

		if(d[y+1][x] < d[y][x] + maps[y+1][x]) 
			 d[y+1][x] = d[y][x] + maps[y+1][x];

		if(d[y+1][x+1] < d[y][x] + maps[y+1][x+1]) 
			 d[y+1][x+1] = d[y][x] + maps[y+1][x+1];
	} 
}

풀이 3

문제의 조건과 이동방법에 대해서
maps[i][j] >= 0; 
대각선 이동은 사용하지 않아도 된다.
대각선 이동은 다른 2가지를 포함한 방법보다 항상 작거나 같다.

#define _CRT_NO_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
using namespace std;

int h, w;
int maps[1001][1001];
int dist[1001][1001];

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin >> h >> w;
	for (int i = 1; i <= h; ++i) 
		for (int j = 1; j <= w; ++j) 
			cin >> maps[i][j];

	for (int y = 1; y <= h; ++y) 
		for (int x = 1; x <= w; ++x) 
			dist[y][x] = max(dist[y - 1][x], dist[y][x - 1]) + maps[y][x];

	cout << dist[h][w];
}

 

풀이 4

재귀 함수를 사용하여 구현해보기.
1.2.3 : 바텀업 = 작은 문제의 답을 이용해서 품, 작은 문제의 답은 항상 존재하므로.

탑-다운
int go(int y, int x) {
	if (y < 1 || x < 1) return 0;
	if (dist[y][x] >= 0) return dist[y][x];
	return dist[y][x] = max(go(y - 1, x), go(y, x - 1)) + maps[y][x];
}
go(h,w);
//모든 칸이 0일 경우 시간초과 가능.(모든 칸이 0일 경우가 존재) 고로 dist를 -1로 초기화 필요.

풀이 5

시작(i, j), 도착(h, w)으로 고정, 

int go(int y, int x) {
	if (y > h || x > w) return 0;
	if (dist[y][x]  >= 0) return dist[y][x];
	return dist[y][x] = max(go(y + 1, x), go(y, x + 1)) + maps[y][x];
}
go(1,1)

 

11060 점프 점프 https://www.acmicpc.net/problem/11060

memo[i] i번째 칸에 도착할 수 있는 최소 점프 횟수

#define _CRT_NO_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;

int maps[1001];
int memo[1001];

int main(void) {
	int n;
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> maps[i];
		memo[i] = -1;
	}
	memo[1] = 0;
	for (int i = 1; i <= n; ++i) {
		if (memo[i] == -1) continue;
		for (int j = 1; j <= maps[i]; ++j) {
			int next = i + j;
			if (next > n) continue;
			if (memo[next] == -1 || memo[next] > memo[i] + 1)
				memo[next] = memo[i] + 1;
		}
	}
	cout << memo[n];
}

15486 퇴사2 https://www.acmicpc.net/problem/15486

크기가 백오십만이므로 전역변수로 처리해도 되지만
메인 함수에 선언하고 싶다면 %100으로 나누어 줘도 된다.

#include <iostream>
#define endl '\n'
using namespace std;

int dist[201];

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n;
	cin >> n;
	int mn = 0;
	for (int i = 1; i <= n; ++i) {
		int t, p;
		cin >> t >> p;
		if(dist[(i + t-1)%100] < mn + p)
		dist[(i + t-1) % 100] = mn + p;
		if (mn < dist[i % 100]) mn = dist[i % 100];
	}
	cout << mn;
}

10942 팰린드롬? https://www.acmicpc.net/problem/10942

수열의 부분 수열이 팰린드롬(Palindrome, 뒤집었을때 같은 문자열)인지 확인하는 문제
한 문자열이 팰린드롬인지 확인하는데 걸리는 시간 : O(N)
질문이 M개면 O(MN)이라는 시간이 걸림. -> 시간초과

 

쿼리 문제 : 뭐가 있을때, 수열에 무언가를 해서 답을 구하는 것. 
쿼리 ij를 실행 했을때, 1 or 0

팰린드롬은 가운데 부터 양쪽을 같은문자를 추가하는 재귀적인 형태로 구성되어 있음.
D[i][j] = maps[i] ~ maps[j]가 팰린드롬이면 1, 아니면 0
홀수 일때, 짝수 일때 구분

maps[i] ~ maps[j]가 팰린드롬이려면
1. maps[i] == maps[j]
2. maps[i+1] ~ maps[j-1]이 팰린드롬이여야 된다.

다이나믹을 먼저 수행하고 쿼리를 구하는 방식 -> O(N^2 + M)

∴일방적인 방식으로 배열을 채우지 않기 때문에 재귀 호출을 사용하는 것이 좋다!
재귀함수는 배열을 채우는 방식을 고려하지 않아도 되기 때문에

재귀를 사용안하고 바텀업 으로 할경우 
길이가 1인것 채우고, 2인것 채우고, 3인것 채우고, ...

 

반례구하기 :

모두 되는것, 모두 안되는것, 최솟값, 최댓값, 등 생각해보기

 

//재귀
#define _CRT_SECURE_NO_WARNINGS 
#include <iostream>
#include <cstring>
#define endl '\n'
using namespace std;
int maps[3000];
int memo[3000][3000]; // i부터j까지가 팰린드롬이면 1

int go(int i, int j) {
	if (i == j) return 1;	//길이 1
	else if (i + 1 == j && maps[i] == maps[j]) return 1;	//길이 2

	if (memo[i][j] >= 0) return memo[i][j];		//메모이제이션

	if (maps[i] != maps[j]) return 0;
	else return memo[i][j] = go(i + 1, j - 1);	
}

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n, m;
	memset(memo, -1, sizeof(memo));
	cin >> n;
	for (int i = 1; i <= n; ++i) 
		cin >> maps[i];

	cin >> m;
	while (m--) {
		int n1, n2;
		cin >> n1 >> n2;
		cout << go(n1, n2) << endl;
	}
}

//bottom-up
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstring>
#define endl '\n'
using namespace std;
int maps[3000];
int memo[3000][3000]; // i부터j까지가 팰린드롬이면 1

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n, m;
	cin >> n;
	for (int i = 1; i <= n; ++i)
		cin >> maps[i];

	for (int i = 1; i <= n; ++i)	//길이 1
		memo[i][i] = 1;
	for (int i = 1; i <= n - 1; ++i)	//길이 2
		if (maps[i] == maps[i + 1]) memo[i][i + 1] = 1;

	for (int k = 3; k <= n; ++k) {
		for (int i = 1; i <= n - k + 1; ++i) { // 시작
			int j = i + k - 1;	// 끝
			if (maps[i] == maps[j] && memo[i + 1][j - 1])
				memo[i][j] = 1;
		}
	}

	cin >> m;
	while (m--) {
		int n1, n2;
		cin >> n1 >> n2;
		cout << memo[n1][n2] << endl;
	}
}

15989 1,2,3더하기 4 https://www.acmicpc.net/problem/15989

순서를 정하자 : 1부터 쓰고, 2 쓰고, 3쓰는 방법만 사용하기.
순서를 정했으므로 중복없이, 모든 경우의 수를 구할 수 있음.

1,2,3더하기 문제에서 이중포문 위치만 서로 바꿔주면 해결되는 문제.

//1,2,3더하기
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#define endl '\n'
using namespace std;

int n, memo[10001];
int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	
	cin >> n;
	memo[0] = 1;
	int dn[3] = { 1, 2, 3 };

	for (int i = 1; i <= 10000; ++i) {
		for (int j = 0; j < 3; ++j) {
			if (i - dn[j] >= 0) memo[i] += memo[i - dn[j]];
		}
	}
	

	while (n--) {
		int num;
		cin >> num;
		cout << memo[num] << endl;
	}
}

//1,2,3더하기4
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#define endl '\n'
using namespace std;

int n, memo[10001];
int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin >> n;
	memo[0] = 1;
	int dn[3] = { 1, 2, 3 };

	for (int j = 0; j < 3; ++j) {
		for (int i = 1; i <= 10000; ++i) {
			if (i - dn[j] >= 0) memo[i] += memo[i - dn[j]];
		}
	}

	while (n--) {
		int num;
		cin >> num;
		cout << memo[num] << endl;
	}
}

11066 파일합치기 https://www.acmicpc.net/problem/11066

n개의 파일이 있을때 연속한 두개의 파일을 합치며 필요한 비용의 총 합의 최솟값을 구하는 문제
파일의 시작위치와 끝위치로 중간 과정을 나눌 수 있음.
d[i][j] = i번 파일부터 j번 파일까지 합치는 최소 비용.

d[i][j] = k는i 부터 j-1까지 ( d[i][k] + d[k+1][j] + 합치는 비용) 중 최솟값 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <cstring>
#define endl '\n'
using namespace std;

int d[501][501];
int a[501];

int go(int i, int j) {
	if (i == j) return 0;
	if (d[i][j] != 0) return d[i][j];
	int ans = 1e9, tmp, sum = 0;
	for (int k = i; k <= j; ++k)
		sum += a[k];
	for (int k = i; k < j; ++k) {
		tmp = go(i, k) + go(k + 1, j) + sum;
		if (ans > tmp) ans = tmp;
	}
	return d[i][j] = ans;
}

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	
	int t, n;
	cin >> t;
	while (t--) {
		cin >> n;
		memset(d, 0, sizeof(d));
		for (int i = 1; i <= n; ++i) 
			cin >> a[i];
		cout << go(1, n)<< endl;
	}
}

 

12865 평범한 배낭 https://www.acmicpc.net/problem/12865

ans를 -1로 초기화 했을 경우, 경우의 수가 없을경우 -1이 출력되니
ans는 최솟값으로 초기화 하자. // 다이나믹은 ans 조차 사용 안해도 ㄱㅊ
반례 : 아예 경우가 없는 경우.

각각의 물건을 배낭에 넣는 경우와 넣지 않는 경우로 생각하면 경우의 수가 너무 많다. 2^N
-> 무게 제한이 있으므로 해결 가능
d[j] = 배낭에 넣은 물건 무게의 합이 j일때, 가치의 최댓값
일차원 다이나믹으로 구성했으므로, 중복없이 배열을 채우려면 뒤에서부터 배열을 채우면 된다.
시간 복잡도 nk

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#define endl '\n'
using namespace std;
 
int d[100001];
 
int main(void) {
    int n, k, ans = 0;
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) {
        int w, v;
        cin >> w >> v;
        for (int j = k-w; j >=0; --j) {
            if (d[j + w] < d[j] + v)
                d[j + w] = d[j] + v;
            if (ans < d[j + w]) ans = d[j + w];
        }
    }
    //cout << ans; 
    cout << d[k]; 
}

 

1495 기타리스트 https://www.acmicpc.net/problem/1495

평범한 배낭과 비슷한 문제.

배열 d[n+1][m]으로 구성해도 되지만, 무의미한 연산을 줄이고 싶어서 queue를 사용해서 구현했다.
그냥 반복문 돌려도 O(nm)으로 가능하다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
#define endl '\n'
using namespace std;

bool d[51][1001];

int main(void) {
	int n, s, m;
	cin >> n >> s >> m;
	int a[51];
	for (int i = 1; i <= n; ++i)
		cin >> a[i];
	d[0][s] = true;
	queue<int > q;
	q.push(s);
	
	for (int i = 1; i <= n; ++i) {
		int qsize = q.size();
		for (int j = 0; j < qsize; ++j) {
			int num = q.front();
			q.pop();
			if (num - a[i] >= 0 && d[i][num - a[i]] == false) {
				d[i][num - a[i]] = true;
				q.push(num - a[i]);
			}
			if (num + a[i] <= m && d[i][num + a[i]] == false) {
				d[i][num + a[i]] = true;
				q.push(num + a[i]);
			}
		}
	}
	int ans = -1;
	while (!q.empty()) {
		if (q.front() > ans)
			ans = q.front();
		q.pop();
	}
	cout << ans;
}

 

12869 뮤탈리스크 https://www.acmicpc.net/problem/12869

3중 배열을 구현해야 되서 조금 햇갈리고 귀찮았던 문제

top-down으로 데미지를 주고 남은 체력을 계산하는 것이 아니라, bottom-up으로 데미지를 준걸로 계산했다.

d[a][b][c] = 데미지를 a, b, c주는데 필요한 최소 공격수

하지만 귀찮아도 구현 가능하다!! (그리고 정리하지 않은 부끄러운 코드..)

//bottom-up
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstring>
#define endl '\n'
using namespace std;

int d[101][101][101];	//a, b, c일때 최솟값.
int dx[6][3] = { 
	{9, 3, 1},{9, 1, 3},
	{3, 9, 1},{1, 9, 3},
	{1, 3, 9},{3, 1, 9}
};

void go(int a, int b, int c) {
	for (int i = 0; i < 6; ++i) {
		if (a + dx[i][0] > 100 || b + dx[i][1] > 100 || c + dx[i][2] > 100) continue;
		if (d[a + dx[i][0]][b + dx[i][1]][c + dx[i][2]] > d[a][b][c] + 1 || d[a + dx[i][0]][b + dx[i][1]][c + dx[i][2]] == 0) {
			d[a + dx[i][0]][b + dx[i][1]][c + dx[i][2]] = d[a][b][c] + 1;
			go(a + dx[i][0], b + dx[i][1], c + dx[i][2]);
		}
	}
}

int main(void) {
	int n;
	cin >> n;
	go(0, 0, 0);
	int a, b=0, c=0, ans = 99999999;

	if(n==3)
		cin >> a >> b >> c;
	else if (n == 2) 
		cin >> a >> b;
	else 
		cin >> a;
	
	for (int i = 0; i <= 100; ++i) {
		for (int j = 0; j <= 100; ++j) {
			for (int k = 0; k <= 100; ++k) {
				if (a <= i && b <= j && c <= k) {
					if (ans > d[i][j][k] && d[i][j][k] != 0 )
						ans = d[i][j][k];
                        
	cout << ans;
}

 

 

10422 괄호 https://www.acmicpc.net/problem/10422

어려워서 해답을 참고했던 문제.

괄호 문자열을 구성하는 방법은 많지만, 간단한 점화식으로 일반화 하긴 어려웠다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#define endl '\n'
#define mod 1000000007
using namespace std;

long long a[5001];
int main(void) {
	int t;
	cin >> t;
	a[0] = 1;
	a[2] = 1;
	a[4] = 2;

	for (int i = 6; i <= 5000; i += 2) {
		for (int j = 2; j <= i; j += 2) {
			a[i] += (a[j - 2] * a[i - j]) % mod;
			a[i] %= mod;
		}
	}

	while (t--) {
		int n;
		cin >> n;
		cout << a[n] << endl;
	}
}