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

    //Target, Pattern
    string T, P;
    getline(cin, T);
    getline(cin, P);

    cout << T << '\n';
    cout << P << '\n';




    return 0;
}

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

1. 문제설명

간선의 cost를 뺏기는 양으로 두면

금을 땅에서 주울 경우에는 마이너스

뺏길 경우는 플러스로 두게 되어 이동하는데 필요한 cost를 설정할 수 있다.

이후 벨만포드 알고리즘을 적용해서 풀면 된다.

단 이 문제의 경우 음의 사이클이 존재한다고 무조건 -1이 될 수 없다.

왜냐하면 음의 사이클이 존재해도 시작점에서 도착점까지 가는데 경유하지 않을 수 있기 때문이다

즉 음의사이클이 존재는 하나 따로 동떨어진 경우가 테스트케이스로 들어올 수도 있다.

그래서 음의사이클이 존재하고 음의사이클에서 도착점으로 가는지 판단해야한다.

또한 출발점 1에서 도착점 n까지 도달할 수 있는지 확인해야한다.

이를 위해 역방향 간선을 저장해두고 n으로부터 시작하여 BFS를 돌면

1과 음의 사이클에서 도착점까지 갈 수 있는지 확인할 수 있다.

2. 문제풀이코드 C++

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

typedef pair<int, int> pi;

const long long INF = 1e18;
long long dist[101];
int pre[101];

int n, m;
vector<pi> adj[101];
vector<pi> rev_adj[101];

bool goal[101];

void check_goal() {
	queue<int> Q;

	Q.push(n);
	goal[n] = 1;

	while (!Q.empty()) {
		int x = Q.front(); Q.pop();
		for (auto &i : rev_adj[x]) {
			int nx = i.first;
			if (goal[nx] == 0) {
				Q.push(nx);
				goal[nx] = 1;
			}
		}
	}
}

void print(int n) {

	if (n == 0) return;
	print(pre[n]);
	cout << n << ' ';
}

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

	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		adj[u].push_back({ v,-w });
		rev_adj[v].push_back({ u,-w });
	}
	
	check_goal();

	//시작점에서 도착점 가는 길이 없는 경우
	if (goal[1] == 0) {
		cout << -1 << '\n';
		return 0;
	}

	fill(dist, dist + 101, INF);

	dist[1] = 0;



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

			for (auto& a : adj[j]) {
				int nx = a.first;
				int d = a.second;

				if (dist[j] != INF && dist[nx] > dist[j] + d) {
					pre[nx] = j;
					dist[nx] = dist[j] + d;

					if ((i == n-1) && (goal[j])) {
						cout << -1 << '\n';
						return 0;
					}
				}
			}
		}
	}


	print(n);


	return 0;
}

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

1.문제설명

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

int n;
bool ch[1001];
struct Hw {
	int day, point;
	bool operator<(const Hw& b) const {
		return point > b.point;
	}
};

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	vector<Hw> v;

	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());

	int ans = 0;
	for (int i = 0; i <v.size(); i++) {
		int day = v[i].day;
		int point = v[i].point;

		while (ch[day] && day>=1) {
			day--;
		}
		if (day == 0) continue;
		ch[day] = 1;
		ans += point;
	}
	
	cout << ans << '\n';
	return 0;
}

2. 우선순위 큐 활용

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

int n;
bool ch[1001];
struct Hw {
	int day, point;
	bool operator<(const Hw& b) const {
		return point < b.point;
	}
};

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	priority_queue<Hw> Q;

	cin >> n;
	for (int i = 0; i < n; i++) {
		int a, b;
		cin >> a >> b;
		Q.push({ a,b });
	}

	int ans = 0;
	while (!Q.empty()) {
		int day = Q.top().day;
		int point = Q.top().point;
		Q.pop();

		while (ch[day] && day>=1) {
			day--;
		}

		if (day == 0) continue;
		ch[day] = 1;
		ans += point;


	}

	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/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/3665

1. 문제설명

단방향 그래프 관계가 주어지고

그래프에서 간선의 방향을 수정했을 때

위상정렬을 수행하면 단 하나의 경우의 수만 나오는지 확인하는 문제다.

2. 접근방법[알고리즘]

우선 위상정렬을 수행하는데 확인해야 할 게 두가지 있다.

첫 번째는

단 하나의 경우의 수만 등장하는지 ==

확실한 순위를 찾을 수 있는지 확인해야한다.

이를 확인하려면 위상정렬을 하면서 큐의 size를 확인해야 한다.

만약 하나의 노드에서 여러 노드로 퍼질 수 있다면

큐의 사이즈가 2를 넘게 되고 이때는 위상정렬의 가짓 수가 여러개가 되어서 확실한 순위를 찾을 수 없다.

두번째는 

사이클이 존재하다면 IMPOSSIBLE을 출력해야한다.

사이클이 존재하면 위상정렬이 불가능하고,

그 경우에 위상정렬 과정에서 degree(차수) 가 0이 되지 않는 노드가 생기기 때문에

모든 노드를 탐색하지 못한다.

3. 문제풀이코드 C++

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

bool adj[501][501];
int degree[501];


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int t;
    cin >> t;
    for (int T = 0; T < t; T++) {

        memset(adj, 0, sizeof(adj));
        memset(degree, 0, sizeof(degree));
        int n;
        cin >> n;

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

		for (int i = 0; i < pre.size(); i++) {
            for (int j = i + 1; j < pre.size(); j++) {
                adj[pre[i]][pre[j]] = 1;
                degree[pre[j]]++;
            }
        }

        int m;
        cin >> m;


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

            if (adj[a][b] == 1) {
                adj[a][b] = 0;
                degree[b]--;
                adj[b][a] = 1;
                degree[a]++;
            }
            else {
                degree[a]--;
                adj[b][a] = 0;
                adj[a][b] = 1;
                degree[b]++;
            }
        }

        
        queue<int> Q;

        for (int i = 1; i <= n; i++) {
            if (degree[i] == 0) {
                Q.push(i);
            }
        }

        vector<int> ans;

        bool cantKnow = false;

        while (!Q.empty()) {

            if (Q.size() >= 2) {
                cantKnow = true;
                break;
            }

            int x = Q.front(); Q.pop();
            ans.push_back(x);

            for (int i = 1; i <= n; i++) {
                if (adj[x][i] == 1) {
                    int nx = i;

                    if (--degree[nx] == 0) {
                        Q.push(nx);
                    }

                }
            }
        }

        if (cantKnow) {
            cout << "?\n";
            continue;
        }


        if (ans.size()!=n) {
            cout << "IMPOSSIBLE\n";
            continue;
        }
        else {
			for (auto x : ans) {
				cout << x << ' ';
			}
			cout << '\n';
        }


    }
  
    return 0;
}

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

1.문제설명

1번에서 2번으로 갈 수 있는 모든 경로를 구해야 한다.

단 한 경로에 포함된 길이 다른 경로에 포함되면 안된다

2.접근방법[알고리즘]

문제가 처음 접했을 때 DFS로 노드를 순환하면서 풀 수 있을 것 같지만

그럴 수 없다.

이 문제는 Network Flow(최대유량) 알고리즘을 알아야 풀 수 있다.

한 간선을 한 번씩 방문할 수 있을 때 2번으로 갈 수 있는 경우가 몇 개 인지 구해야한다.

한 간선을 한 번씩 방문할 수 있다는 말은

한 간선에 1명만 이동할 수 있다는 말과 같고

이 때 2번으로 총 몇명이 도착 할 수 있는지 최대유량을 구해야 하는 문제다.

3.문제풀이코드 C++

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

const int MAX = 401;

int n, p,res;
int c[MAX][MAX], f[MAX][MAX], d[MAX];
vector<int> adj[MAX];

void maxFlow(int start, int end) {
    while (1) {
		fill(d, d + MAX, -1);
        queue<int> Q;
        d[start] = 0;
        Q.push(start);

        while (!Q.empty() && d[end] == -1) {
            int x = Q.front();
            Q.pop();
            for (int i = 0; i < adj[x].size(); i++) {
                int nx = adj[x][i];

                if (d[nx] == -1 && c[x][nx] - f[x][nx] > 0) {
                    Q.push(nx);
                    d[nx] = x;
                    if (nx == end) break;
                }
            }
        }

        if (d[end] == -1) break;

        int flow = INT_MAX;
        for (int i = end; i != start; i = d[i]) {
            flow = min(flow, c[d[i]][i] - f[d[i]][i]);
        }
        for (int i = end; i != start; i = d[i]) {
            f[d[i]][i] += flow;
            f[i][d[i]] -= flow;
        }

        res += flow;
    }


}

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

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

        c[a][b] = 1;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    maxFlow(1, 2);

    cout << res << '\n';
   

    return 0;
}

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

1.문제설명

INPUT

5
0 6 15 2 6
6 0 9 8 12
15 9 0 16 18
2 8 16 0 4
6 12 18 4 0

OUTPUT

55

문제에서 N개의 노드가 있을 때

노드에서 노드로 가는 모든 최단 거리를 INPUT으로 준다.

주어진 노드간 최단 거리를 유지하면서 간선의 개수를 최소로 할 때 

간선의 거리의 합을 구해야 한다.

2.접근방법[알고리즘]

주어진 인풋을 dist배열에 넣고

플로이드 워셜을 한번 실행했을 때

dist[i][k] + dist[k][j]) == dist[i][j]

이런 상황이 있으면 간선을 최소로 하기위해

dist[i][j] 의 간선을 사용하지 않고

dist[i][k] 와 dist[k][j]의 간선만 사용하면 된다.

맨 처음엔 문제에서 주어진 인풋의 간선을 모두 사용하는 걸 전제로 하고

위와 같은 간선이 있으면 i - j 를 이어주는 간선을 없애주면

최소 간선을 구해낼 수 있다.

for (int k = 0; k < n; k++) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (i == j || j == k || i == k) continue;
				if ((dist[i][k] + dist[k][j]) == dist[i][j]) {
					arr[i][j] = INF;
				}
				else if (dist[i][k] + dist[k][j] < dist[i][j]) {
					cout << -1 << '\n';
					return 0;
				}
			}
		}
	}

3. 문제풀이코드 C++

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


const int INF = 0x3f3f3f3f;

int n, arr[21][21];

int dist[21][21];
bool ch[21][21];
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	memset(dist, 0x3f, sizeof(dist));

	cin >> n;

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

	for (int k = 0; k < n; k++) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (i == j || j == k || i == k) continue;
				if ((dist[i][k] + dist[k][j]) == dist[i][j]) {
					arr[i][j] = INF;
				}
				else if (dist[i][k] + dist[k][j] < dist[i][j]) {
					cout << -1 << '\n';
					return 0;
				}
			}
		}
	}

	int sum = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (arr[i][j] < INF) sum += arr[i][j];
		}
	}

	cout << sum / 2 << '\n';



	return 0;
}