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

#include <bits/stdc++.h>
#include <unordered_set>
using namespace std;



int n, k;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> k;

	vector<int> v;
	for (int i = 0; i < k; i++) {
		int tmp;
		cin >> tmp;
		v.push_back(tmp);
	}

	unordered_set<int> set;

	int ans = 0;
	for (int i = 0; i < k; i++) {
		int tmp = v[i];

		if (set.size() < n) {
			set.insert(tmp);
		}
		else if(set.size()==n) {
			if (set.count(tmp)) {
				continue;
			}
			else {
				map<int, int> m;

				for (auto x : set) {
					m[x] = 1000;
				}

				for (int j = i + 1; j < k; j++) {
					if (set.count(v[j])) {
						m[v[j]] = min(m[v[j]], j);
					}
				}

				int maxx = 0;
				int max_id = -1;

				for (auto x : set) {
					if (maxx < m[x]) {
						maxx = m[x];
						max_id = x;
					}
				}
				set.erase(max_id);
				set.insert(tmp);
				
				ans++;
			}
		}

	}

	cout << ans << '\n';


	return 0;
}

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

#include <bits/stdc++.h>
using namespace std;

int n;
vector<pair<int, int> > v;
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n;
	for (int i = 0; i < n; i++) {
		int a, b;
		cin >> a >> b;

		v.push_back({ a,b });
	}

	sort(v.begin(), v.end());

	priority_queue<int> Q;

	for (int i = 0; i < n; i++) {
		if (i == 0) {
			Q.push(-v[i].second);
			continue;
		}

		if (v[i].first >= -Q.top()) {
			Q.pop();
			Q.push(-v[i].second);
		}
		else {
			Q.push(-v[i].second);
		}
	}

	cout << Q.size() << '\n';


	return 0;
}

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

1.문제설명

이 문제의 답을 구하는 방법은 크게 두가지가 있습니다.

첫번째는

123~987중에서 조건이 주어질 때마다 정답이 될 수 있는 후보만 남겨주는 것입니다.

두번째는

조건에 부합하는 숫자의 집합을 구해서 모든 조건의 교집합을 구해내는 것입니다.

첫번째로 구하는게 123~987 내에서 계산하는 숫자를 계속 좁혀나가니까 효율적입니다.

저는 처음에 든생각이 두번째로 푸는거라 이악물고 풀었는데 답이 나오네요

테스트케이스가 워낙 작아서 두번째도 가능합니다.

두가지방법 모두 코드를 올립니다.

2.문제풀이코드 C++

첫번째 방법

#include <bits/stdc++.h>
using namespace std;

int n;
bool ch[1000];

void compare(int x, int y, int z) {

	for (int i = 123; i <= 987; i++) {
		if (ch[i]) {
			int s = 0, b = 0;

			int arr1[3] = { i / 100, (i % 100) / 10 ,i % 10 };
			int arr2[3] = { x / 100, (x % 100) / 10 ,x % 10 };


			for (int j = 0; j < 3; j++) {
				for (int k = 0; k < 3; k++) {
					if(j==k && (arr1[j]==arr2[k])){
						s++;
					}
					else if (j != k && arr1[j] == arr2[k]) {
						b++;
					}
				}
			}

			//후보에서 제외
			if (!(y == s && z == b)) {
				ch[i] = 0;
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n;
	//ch배열 초기화 
	for (int i = 1; i <= 9; i++) {
		for (int j = 1; j <= 9; j++) {
			for (int k = 1; k <= 9; k++) {
				if (i != j && k != j && i != k) {
					ch[i * 100 + 10 * j + k] = 1;
				}
			}
		}
	}


	for (int i = 0; i < n; i++) {
		int x, y, z;
		cin >> x >> y >> z;
		compare(x, y, z);
	}


	int ans = 0;
	for (int i = 0; i < 1000; i++) {
		if (ch[i]) ans++;
	}

	cout << ans << '\n';

	return 0;
}

두번째 방법

#include <bits/stdc++.h>
using namespace std;

int n;
bool ch[101][1000];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n;

	for (int i = 0; i < n; i++) {
		int a, s, b;
		cin >> a >> s >> b;

		int x = a / 100;
		int y = (a % 100) / 10;
		int z = a % 10;

		if (s == 3 && b == 0) {
			cout << 1 << '\n';
			return 0;
		}
		else if (s == 0 && b == 3) {
			ch[i][z * 100 + x * 10 + y] = 1;
			ch[i][y * 100 + z * 10 + x] = 1;
		}
		else if (s == 1 && b == 2) {
			ch[i][100 * x + 10 * z + y] = 1;
			ch[i][100 * z + 10 * y + x] = 1;
			ch[i][100 * y + 10 * x + z] = 1;
		}
		else if (s == 2 && b == 0) {
			for (int j = 1; j <= 9; j++) {
				if (j != z && j != x && j != y) {
					ch[i][100 * x + 10 * y + j] = 1;
					ch[i][100 * x + 10 * j + z] = 1;
					ch[i][100 * j + 10 * y + z] = 1;
				}
			}
		}
		else if (s == 1 && b == 1) {
			for (int j = 1; j <= 9; j++) {
				if (j != z && j != x && j != y) {
					ch[i][100 * x + 10 * j + y] = 1;
					ch[i][100 * x + 10 * z + j] = 1;
					ch[i][100 * z + 10 * y + j] = 1;
					ch[i][100 * j + 10 * y + x] = 1;
					ch[i][100 * j + 10 * x + z] = 1;
					ch[i][100 * y + 10 * j + z] = 1;
				}
			}
		}
		else if (s == 0 && b == 2) {
			for (int j = 1; j <= 9; j++) {
				if (j != z && j != x && j != y) {
					ch[i][100 * j + 10 * x + y] = 1;
					ch[i][100 * y + 10 * x + j] = 1;
					ch[i][100 * y + 10 * j + x] = 1;
					ch[i][100 * z + 10 * j + x] = 1;
					ch[i][100 * z + 10 * x + j] = 1;
					ch[i][100 * j + 10 * z + x] = 1;
					ch[i][100 * z + 10 * j + y] = 1;
					ch[i][100 * y + 10 * z + j] = 1;
					ch[i][100 * j + 10 * z + y] = 1;
				}
			}
		}
		else if (s == 1 && b == 0) {
			for (int j = 1; j <= 9; j++) {
				for (int k = 1; k <= 9; k++) {
					if (j != z && j != x && j != y && j != k && k != x && k != y && k != z) {
						ch[i][100 * x + 10 * j + k] = 1;
						ch[i][100 * j + 10 * y + k] = 1;
						ch[i][100 * j + 10 * k + z] = 1;
					}
				}
			}
		}
		else if (s==0 && b == 1) {
			for (int j = 1; j <= 9; j++) {
				for (int k = 1; k <= 9; k++) {
					if (j != z && j != x && j != y && j != k && k != x && k != y && k != z) {
						ch[i][100 * j + 10 * x + k] = 1;
						ch[i][100 * j + 10 * k + x] = 1;

						ch[i][100 * y + 10 * j + k] = 1;
						ch[i][100 * j + 10 * k + y] = 1;

						ch[i][100 * z + 10 * j + k] = 1;
						ch[i][100 * j + 10 * z + k] = 1;

					}
				}
			}
		}
		else if (s == 0 && b == 0) {
			for (int j = 1; j <= 9; j++) {
				for (int k = 1; k <= 9; k++) {
					for (int t = 1; t <= 9; t++) {
						if (j != z && j != x && j != y && j != k && k != x && k != y && k != z
							&& x != t && y != t && z != t && k != t && j != t) {
							ch[i][100 * j + 10 * t + k] = 1;
						}
					}
				}
			}

		}
	}

	int ans = 0;

	for (int i = 100; i < 1000; i++) {
		bool flag = true;
		for (int j = 0; j < n; j++) {
			if (ch[j][i] == 0) {
				flag = false;
				break;
			}
		}
		if (flag) ans++;
	}

	cout << ans << '\n';
	return 0;
}

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

1.문제설명

1. 서로 다른 사탕이 있으면 바꾼다.

2. 모든 행과 열에서 연속되는 최대 사탕의 수를 구해본다.

3. 1과 2를 모든 영역에 대해 반복해야한다.

2.문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;

int n, ans;
char arr[51][51];

int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

void Count() {
	for (int i = 0; i < n; i++) {
		int comp = arr[i][0];
		int cnt = 1;
		for (int j = 1; j < n; j++) {
			if (comp == arr[i][j]) {
				cnt++;
			}
			else {
				comp = arr[i][j];
				ans = max(ans, cnt);
				cnt = 1;
			}
		}
		ans = max(ans, cnt);
	}

	for (int i = 0; i < n; i++) {
		int comp = arr[0][i];
		int cnt = 1;
		for (int j = 1; j < n; j++) {
			if (comp == arr[j][i]) {
				cnt++;
			}
			else {
				comp = arr[j][i];
				ans = max(ans, cnt);
				cnt = 1;
			}
		}
		ans = max(ans, cnt);
	}

}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n;
	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		for (int j = 0; j < n; j++) {
			arr[i][j] = s[j];
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {

			for (int k = 0; k < 4; k++) {
				int nx = i + dx[k];
				int ny = j + dy[k];

				if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
				if (arr[i][j] != arr[nx][ny]) {
					swap(arr[i][j], arr[nx][ny]);
					Count();
					swap(arr[i][j], arr[nx][ny]);
				}
			}
		}
	}
	
	cout << ans << '\n';


	return 0;
}

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

1.문제설명

처음 봤을 때 이게 왜 다이나믹 프로그래밍 문제일까 의문이 드는 문제입니다.

어떻게 다이나믹 프로그래밍으로 구현해야할지 고민이 필요합니다.

다이나믹 프로그래밍의 핵심은

주어진 문제를 여러개의 부분 문제로 나누어 풀고

그 결과를 이용해서 주어진 문제를 해결 하는 것입니다.

주어진 S 문자열의 0번 char부터 A 집합의 문자열들과 서로 비교하면서

A의 문자열이 S문자열의 부분과 일치하는지 확인합니다.

이 과정을 반복해서 S문자열의 몇번째 char 까지 만들 수 있는지

bool자료형의 dp 배열에 저장해두면서 그 이후의 부분을 만들 수 있는지 판단하면 됩니다.

그림을 보면 이해하기 쉬울겁니다.

softwarecontest와 software이 7번째 까지 일치하니까

dp[8] = true로 만들어줍니다

7이 아니라 8에 두는 건 인덱스 관리가 7에두는 것보다 다음 숫자인 8에 두는게 쉽기 때문입니다.

그 후 dp배열을 확인하면서 dp[i] == 1 인 지점부터 다시 A의 문자열들과 비교해줍니다

software은 다르니까 넘어가게 되고 contest가 8번부터 일치하므로 다시 dp[15] == 1로 만들어줍니다.

결과상 dp[S.length()] == 1 이라면 문자열 S를 만들 수 있다는 뜻입니다.

2.문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;

int n;
bool dp[101];
string s;
vector<string> A;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> s;
	cin >> n;
	
	for (int i = 0; i < n; i++) {
		string tmp;
		cin >> tmp;
		A.push_back(tmp);
	}

	for (int i = 0; i < s.length(); i++) {
		if (dp[i] || i==0) {
			int st = i;
			
			for (int j = 0; j < n; j++) {
				//부분문자열을 합칠 때 원래 문자열보다 더 길어지는 경우는 제외
				if (st + A[j].length() > s.length()) continue;

				bool flag = true;
				for (int k = 0; k < A[j].length(); k++) {
					if (A[j][k] != s[st + k]) {
						flag = false;
						break;
					}
				}

				if (flag) {
					dp[st + A[j].length()] = 1;
				}
			}
		}
	}

	cout << dp[s.length()];


	return 0;
}

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

#include <bits/stdc++.h>
using namespace std;

int n, k, arr[10001];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> k;

	fill(arr, arr + 10001, INT_MAX);

	for (int i = 0; i < n; i++) {
		int num;
		cin >> num;

		for (int j = 1; j <= k; j++) {
			if (j % num == 0) 
				arr[j] = min(arr[j], j / num);
                
			if(j-num >0 && arr[j-num]!=INT_MAX) 
				arr[j] = min(arr[j], arr[j - num] + 1);

		}

	}
	if (arr[k] == INT_MAX) cout << -1;
	else cout << arr[k];

	return 0;
}

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

1. 문제설명

주사위를 굴려서 이동시키는 과정을 잘 구현하는게 핵심인 문제다.

  2
4 1 3
  5
  6

문제에서 주는 이 전개도를 잘 관찰해야 한다.

이렇게 주사위가 있을 때

주사위는 6칸이므로 6칸에 어떤 숫자가 저장되는지

int 배열 arr[6]에 해당 면에 있는 숫자를 저장할 수 있다.

항상 맨윗면은 1번, 동쪽을 보는 면은 3번 이런식으로 주사위의 면을 고정한 채로

주사위를 굴리는 행위를 할 때마다

각 면에 저장된 숫자를 서로 바꿔주면 주사위를 굴리는 행위를 구현할 수 있다.

    [2]
     0  
[4] [1] [3] [6]
 0   0   0   0
    [5]
     0
    [6]
     0

위 전개도를 기준으로 주사위의 배열 방이 [1]번부터 [6]까지 있고

그 안에 해당하는 값이 있으면

주사위를 굴릴 때마다 해당 값들을 바꿔주면 된다.

[6]번은 주사위의 아랫면에 해당하므로

동서로 굴릴 때나 남북으로 굴릴때나 변환되어야 한다.

2.문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;

int n, m, x, y, k;
int arr[21][21];
int dice[7];

void copy_ground() {
	if (arr[x][y] == 0) {
		arr[x][y] = dice[6];
	}
	else {
		dice[6] = arr[x][y];
		arr[x][y] = 0;
	}

	cout << dice[1] << '\n';
}

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

	cin >> n >> m >> x >> y >> k;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> arr[i][j];
		}
	}

	int order;
	for (int i = 0; i < k; i++) {
		cin >> order;

		if (order == 1) {
			if (y + 1 < m) {
				y++;
				int tmp = dice[1];
				dice[1] = dice[4];
				dice[4] = dice[6];
				dice[6] = dice[3];
				dice[3] = tmp;
				copy_ground();
			}
		}
		else if (order == 2) {
			if (y - 1 >= 0) {
				y--;
				int tmp = dice[1];
				dice[1] = dice[3];
				dice[3] = dice[6];
				dice[6] = dice[4];
				dice[4] = tmp;
				copy_ground();
			}
		}
		else if (order == 3) {
			if (x - 1 >= 0) {
				x--;
				int tmp = dice[2];
				dice[2] = dice[1];
				dice[1] = dice[5];
				dice[5] = dice[6];
				dice[6] = tmp;
				copy_ground();
			}
		}
		else if (order == 4) {
			if (x + 1 < n) {
				x++;

				int tmp = dice[1];
				dice[1] = dice[2];
				dice[2] = dice[6];
				dice[6] = dice[5];
				dice[5] = tmp;
				copy_ground();
			}
		}
	}


	return 0;
}

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

1. 문제설명

외판원 순회 문제입니다.

시작점을 정해주지 않았기 때문에 모든 노드에서 시작할 수 있습니다.

우선순위큐를 이용해서 최단거리를 우선으로 방문해야 메모리와 시간을 아낄 수 있습니다.

시험삼아 우선순위큐만 큐로 바꿔서 돌려봤습니다.

메모리 63072KB, 360ms 걸린 게 일반 큐를 이용한 것이고

메모리 2500KB, 4ms가 우선순위 큐를 이용한 것입니다.

메모리와 시간차이가 나는 이유는

우선순위큐를 이용할 때는 최단거리를 우선으로 방문하고 그 이외에는 방문하지 않는데

큐를 이용할 때는 이미 방문했던 점이 최단거리가 아닐 수 있기 때문에

계속해서 해당 노드의 해당 상태에 대해 불필요한 계산이 이루어져서

시간과 메모리가 많이 사용됩니다.

2.문제풀이코드 C++

#include <bits/stdc++.h>

int ch[11][1 << 11];
int n, arr[11][11];

struct Node {
	int cur, vis, st, dist;
	bool operator<(const Node& b) const {
		return dist > b.dist;
	}
};

using namespace std;
int main() {


	priority_queue<Node> Q;

	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];
		}
		Q.push({ i,1 << i,i ,0 });
	}

	int ans = INT_MAX;

	while (!Q.empty()) {
		int cur = Q.top().cur;
		int vis = Q.top().vis;
		int st = Q.top().st;
		int dist = Q.top().dist;
		Q.pop();

		ch[cur][vis] = 1;

		if (vis == (1 << n) - 1) {
			if (arr[cur][st] != 0) ans = min(ans, dist + arr[cur][st]);
		}

		for (int i = 0; i < n; i++) {
			if (arr[cur][i] > 0 && ch[cur][vis | (1 << i)] == 0) {
				Q.push({ i,vis | (1 << i),st,dist + arr[cur][i] });
			}
		}
	}
	cout << ans << '\n';


	return 0;
}