이것 저것 &

문제링크: www.acmicpc.net/problem/17822

개인적으로 많이 예외를 못찾아서 고민한 문제....

이런 문제일수록 구현을 간단하게 설계해야 한다.

구현해야할 것은 크게 

• 0. 입력
• 1. 원판 돌리기
• 2. 인접한 수 탐색
• 2-1. 인접한 수 지우기
• 2-2.  평균값에서 감산, 가감하기
• 3. 결과 도출

깨알팁 tip)

1. 원판 돌리기 같은경우에 시계 반대 방향은 m - k 번 시계방향으로 돌리는 것과 같다.

2. 인접한 수를 탐색하는 bfs 구현시 배열을 통해서 구현 범위를 줄일 수 있다.

아래는 정답 코드입니다.

#include <iostream>
#include <cstring>
#include <queue>
#include <cmath>
using namespace std;

int n, m, t;
int arr[51][51] = { 0, };
int result = 0;
int temp[51] = { 0, };
int visited[51][51];

int y_ar[4] = { 1,-1,0,0 };
int x_ar[4] = { 0,0,1,-1 };

//2. search
bool bfs(int y, int x) {

	memset(visited, 0, sizeof(visited));

	queue <pair<int, int>> que;
	que.push(make_pair(y, x));
	visited[y][x] = 1;

	while (!que.empty()) {
		int cy = que.front().first;
		int cx = que.front().second;
		que.pop();

		for (int i = 0; i < 4; i++) {
			int ny = cy + y_ar[i];
			int nx = cx + x_ar[i];

			if (ny < 0 || ny == n) continue;

			if (nx == m) nx = 0;
			else if (nx == -1) nx = m - 1;

			if (visited[ny][nx] == 0 && arr[ny][nx] == arr[cy][cx]) {
				que.push(make_pair(ny, nx));
				visited[ny][nx] = visited[cy][cx] + 1;
			}

		}
	}

	//erase
	bool jud = false;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			if (visited[i][j] > 1)
				jud = true;
	if (jud == true) {
		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++)
				if (visited[i][j] != 0)
					arr[i][j] = 0;
	}
	return jud;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	//0. init
	cin >> n >> m >> t;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			cin >> arr[i][j];

	while (t--) {
		int x, d, k;
		cin >> x >> d >> k;
		if (d == 1)
			k = m - k;
		//1. 회전
		for (int i = x - 1; i < n; i += x) {
			
			for (int l = 0; l < k; l++) {
				for (int j = 0; j < m; j++)
					temp[j] = arr[i][j];

				for (int j = 1; j < m; j++)
					arr[i][j] = temp[j - 1];
				arr[i][0] = temp[m - 1];
			}
		}



		
		bool jud = false;
		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++) {
				if (visited[i][j] == 0 && arr[i][j] != 0) {
					
					bool temp = bfs(i, j);
					if (temp == true)
						jud = true;
				}
			}

		//평균값 구해서 +1, -1  해주기
		if (jud == false) { 
			double sum = 0;
			double cnt = 0;
			for (int i = 0; i < n; i++)
				for (int j = 0; j < m; j++)
					if (arr[i][j] != 0 ) {
						sum += arr[i][j];
						cnt += 1;
					}
			if (cnt > 0) {
				sum = sum / cnt;
				for (int i = 0; i < n; i++)
					for (int j = 0; j < m; j++)
						if (arr[i][j] != 0) {
							if (sum > arr[i][j])
								arr[i][j] ++;
							else if (sum < arr[i][j])
								arr[i][j] --;
						}
			}
		}


	}


	//result
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			result += arr[i][j];
	cout << result << endl;

	
}

문제링크: www.acmicpc.net/problem/12996

dp 문제입니다.

아이디어 도출이 어려운 문제지만 구현난이도는 최하입니다.

3명의 친구들이 불러야 하는 곡수와 전체곡의 갯수가 주어지기 때문에 

long long dp[51][51][51][51]; // s,dotorya, kesakiyo, hongjun7 라는 dp배열을 만들어 메모이제이션 하면 됩니다.

dp[s][d][k][h]는 s곡 남았을때, 1번 친구가 d개 남고, 2번 친구가 k개 남고, 3번 친구가 h개 남았을때의 최대값을 저장합니다.

아래는 정답코드입니다. 막상 구현하니 너무 간단하네요.

주의할 점은 long long을 사용해야 한다는것입니다. 

#include <iostream>
#include <cstring>
using namespace std;

long long dp[51][51][51][51]; // s,dotorya, kesakiyo, hongjun7

long long solved(int s, int d, int k, int h) {

	if (s == 0) {
		if (d == 0 && k == 0 && h == 0)
			return 1;
		else
			return 0;
	}
	
	long long& ret = dp[s][d][k][h];
	if (ret != -1)
		return ret;
	ret = 0;

	ret += solved(s - 1, d - 1, k, h);
	ret += solved(s - 1, d, k - 1, h);
	ret += solved(s - 1, d, k, h - 1);

	ret += solved(s - 1, d - 1, k - 1, h);
	ret += solved(s - 1, d - 1, k, h - 1);
	ret += solved(s - 1, d, k - 1, h - 1);

	ret += solved(s - 1, d - 1, k - 1, h - 1);

	ret %= 1000000007;
	return ret;
}

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

	int s, d, k, h;
	cin >> s >> d >> k >> h;

	memset(dp, -1, sizeof(dp));
	cout << solved(s, d, k, h) << endl;

	return 0;
}

문제링크:www.acmicpc.net/problem/17404

전형적인 dp문제입니다.

근데 문제조건처럼 1과 n이 연결되어 있다는 것을 인지해야합니다.

구현방법은 간단합니다.

첫번째의 시작점을 정해두고 dp를 구하면 됩니다. 이렇게 3번 반복하며 시작점과 끝점의 값이 다르도록 구현하는 것이 핵심입니다.

위 설명과 아래 주석을 함께 보시면 이해하는데 어려움 없을 겁니다!

아래는 정답코드입니다.

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


int n = 0, result = 1000000000;
int arr[1001][3] = { 0, };
int dp[1001][3] = { 0, };

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> n;
	for (int i = 1; i <= n; i++)
		for(int j=0;j<3;j++)
			cin >> arr[i][j];

	for (int k = 0; k < 3; k++) {

		//1. 초기값 설정
		for (int i = 0; i < 3; i++)
			dp[1][i] = 1000000000;
		dp[1][k] = arr[1][k];

		
		//2. 이후 계산
		for (int i = 2; i <= n; i++) {
			dp[i][0] = arr[i][0] + min(dp[i - 1][1], dp[i - 1][2]);
			dp[i][1] = arr[i][1] + min(dp[i - 1][2], dp[i - 1][0]);
			dp[i][2] = arr[i][2] + min(dp[i - 1][0], dp[i - 1][1]);
		}

		//3. 초기값이 아닌 경우에만 result 도출
		for (int i = 0; i < 3; i++) {
			if (k == i) continue;
			result = min(result, dp[n][i]);
		}
	}

	cout << result << endl;
	return 0;
}

문제링크: www.acmicpc.net/problem/1949

• '우수 마을'로 선정된 마을 주민 수의 총 합을 최대로 해야 한다.
• 마을 사이의 충돌을 방지하기 위해서, 만일 두 마을이 인접해 있으면 두 마을을 모두 '우수 마을'로 선정할 수는 없다. 즉 '우수 마을'끼리는 서로 인접해 있을 수 없다.
• 선정되지 못한 마을에 경각심을 불러일으키기 위해서, '우수 마을'로 선정되지 못한 마을은 적어도 하나의 '우수 마을'과는 인접해 있어야 한다.

위

3가지 조건을 통해서 점화식을 도출해야 합니다.

문제 접근 방법:

1. 모든 경우의 수를 비교해주어야 하는 것을 인지

2. 수의 범위가 10000임으로 일반적인 dfs 를 쓰면 시간 초과가 남을 인지

3. dp방식을 통해서 한번 확인한 마을이라면 마킹을 해두며 진행해야함을 인지

점화식은 

일반 마을 = 인접 마을 중에서 최대값

우수 마을 = 인접 마을 중에서 일반 마을들의 최대값 

이고 up-down방식으로 구현했습니다.

아래는 정답 코드입니다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n = 0;
bool visited[10001] = { 0, };
int cost[10001] = { 0, };
vector <int> arr[10001];
int dp[10001][2];
void dfs(int current) {
	if (visited[current])
		return;
	
	visited[current] = 1;
	int& normal = dp[current][0];
	int& greated = dp[current][1];
	normal = 0;
	greated = cost[current];
	for (int i = 0; i < arr[current].size(); i++) {
		int num = arr[current][i];
		if (visited[num] == 1) continue;

		dfs(num);
		normal += max(dp[num][1], dp[num][0]);
		greated += dp[num][0];
		
	}
}



int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> cost[i];
	}

	for (int i = 0; i < n - 1; i++) {
		int t1, t2;
		cin >> t1 >> t2;
		arr[t1].push_back(t2);
		arr[t2].push_back(t1);
	}

	dfs(1);

	cout << max(dp[1][0],dp[1][1]) << endl;

	return 0;
}

dfs를 먼저 호출하고 해당 값들에 넣어주어야지 값들이 올바르게 들어갑니다.

문제링크:www.acmicpc.net/problem/2666

dp문제입니다.

우선 벽장문을 이동할 때, 가장 가까운 문을 옮기는 그리디적인 방식이 항상 최선이 아니라는 것을 알아야 합니다.

ex) 1 0 0 0 1 0 이런식으로 문이 있을때 3번으로 가야한다면 1번문을 이동할건가요? 5번문을 이동할건가요?

즉 모든 경우를 다 고려해주어야 합니다. 이때 시간의 효율성을 위해 dp를 사용해야합니다. 

즉, 이전에 방문했던 값을 마킹해두며 진행해야 합니다.

dp를 사용해야하는 것을 인지했으면, 점화식을 도출해야 합니다.

dp[1번 문위치][2번 문위치][현재 인덱스] = min( 1번 문위치 옮겼을때 최소값, 2번 문위치 옮겼을때 최소값)

이를 토대로 top-down 방식을 사용해서 구현했습니다.

재귀식은 이렇게 구현했습니다.

int solved(int o1, int o2,int cnt) {

	if (cnt == k + 1)
		return 0;

	int &ret = dp[o1][o2][cnt];
	if (ret != -1)
		return ret;
	ret = 0;
	ret = min(abs(arr[cnt] - o1) + solved(arr[cnt], o2, cnt + 1), abs(arr[cnt] - o2) + solved(o1, arr[cnt], cnt + 1));
	return ret;
}

아래는 정답코드입니다.

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

int n = 0, k = 0;
int open1, open2;
int arr[21] = { 0, };
int dp[21][21][21];

int solved(int o1, int o2,int cnt) {

	if (cnt == k + 1)
		return 0;

	int &ret = dp[o1][o2][cnt];
	if (ret != -1)
		return ret;
	ret = 0;
	ret = min(abs(arr[cnt] - o1) + solved(arr[cnt], o2, cnt + 1), abs(arr[cnt] - o2) + solved(o1, arr[cnt], cnt + 1));
	return ret;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	memset(dp, -1, sizeof(dp));

	cin >> n;
	cin >> open1 >> open2;
	cin >> k;
	for (int i = 1; i <= k; i++)
		cin >> arr[i];

	cout<<solved(open1, open2, 1)<<endl;


	return 0;
}

문제링크:www.acmicpc.net/problem/2698

전형적인 dp문제입니다.

결과를 도출할때 2가지로 나누어 생각했습니다.

• 끝이 0일때,
• 끝이 1일때

만약 n=4, k=1일때, 경우의수는 

1100

0110

0011

1101

1011

이렇게 5가지 입니다.

즉, 

i는 n, j는 k 값일때

각각

dp[idp[i][j][0] = dp[i - 1][j][0] + dp[i - 1][j][1]
dp[i][j][1] = dp[i - 1][j][0] + dp[i - 1][j - 1][1]

아래는 정답코드입니다.

#include <iostream>
using namespace std;
int t,n, k;
int dp[101][101][2] = { 0, };
int main() {

	cin >> t;
	
	dp[1][0][0] = 1; //n k 마지막수가 0인지 1인지
	dp[1][0][1] = 1;

	for (int i = 2; i <=100; i++) {
		for (int j = 0; j < i; j++) {
			dp[i][j][0] = dp[i - 1][j][0] + dp[i - 1][j][1];
			dp[i][j][1] = dp[i - 1][j][0] + dp[i - 1][j - 1][1];
		}
	}
	while (t--) {
		cin >> n >> k;
		cout << dp[n][k][0] + dp[n][k][1] << "\n";

	}
	
}

문제풀이:www.acmicpc.net/problem/9251

LCS알고리즘에 대한 설명은 아래 링크를 참고해주세요.

gusdnr69.tistory.com/192

아래는 정답코드입니다.

 LCS2, 팰린드롬 문제들도 함께 풀어보시면서 익혀보세요.

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

string a, b;
int dp[1001][1001] = { 0, };
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	string temp1, temp2;
	cin >> temp1 >> temp2;

	a = ' ' + temp1;
	b = ' ' + temp2;

	for (int i = 1; i < b.size(); i++) {
		for (int j = 1; j < a.size(); j++) {
			if (b[i] == a[j]) dp[i][j] = dp[i - 1][j - 1] + 1;
			else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
		}
	}

	cout << dp[b.size() - 1][a.size() - 1] << endl;


	return 0;
}

문제링크:www.acmicpc.net/problem/9252

LCS문제입니다.

LCS에 대한 설명은 아래 링크를 참고하세요

gusdnr69.tistory.com/192

해당 문제에서는 부분수열을 출력해야합니다.

이때 역순으로 올라가면서 하나씩 저장해준후에, 

역순으로 출력해주면 됩니다.

아래는 알파벳을 저장하는 코드입니다.

	int col = a.size() - 1;
	int row = b.size() - 1;

	while (dp[row][col]) {

		if (dp[row][col] == dp[row - 1][col]) {
			row--;
		}
		else if (dp[row][col] == dp[row][col - 1]) {
			col--;
		}
		else {
			result += a[col];
			row--, col--;
		}

	}

아래는 전체 정답코드입니다.

#include<iostream>
#include <string>
#include <algorithm>
using namespace std;
string a, b;
string result;
int dp[1001][1001] = { 0, };

int main() {

	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	string temp1, temp2;
	cin >> temp1;
	cin >> temp2;
	
	a = ' ' + temp1;
	b = ' ' + temp2;
	
	
	for (int i = 1; i < b.size(); i++) {
		for (int j = 1; j < a.size(); j++) {
			if (a[j] == b[i]) dp[i][j] = dp[i - 1][j - 1] + 1;
			else
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
		}
	}

	
	
	int col = a.size() - 1;
	int row = b.size() - 1;

	while (dp[row][col]) {

		if (dp[row][col] == dp[row - 1][col]) {
			row--;
		}
		else if (dp[row][col] == dp[row][col - 1]) {
			col--;
		}
		else {
			result += a[col];
			row--, col--;
		}

	}

	cout << dp[b.size() - 1][a.size() - 1] << endl;
	if (result.size() > 0) {
		reverse(result.begin(), result.end());
		cout << result << endl;
	}
	return 0;
}

a와 b 앞에 ' '를 추가해주면서 1base로 시작할 수 있도록 만들었습니다.