반응형
https://www.acmicpc.net/category/detail/4580
25/10/16
백준 34552번~ 34562번까지 총 11문제로 이루어져 있다.
문제에서 주어진 그대로 구현하면 된다.
// 34552번 디딤돌 장학금
// 구현
#include <iostream>
#include <vector>
using namespace std;
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl '\n'
int main(void){
fastio
vector<int> M(11);
for (int i = 0; i < 11; ++i) cin >> M[i];
int N; cin >> N;
int ans = 0;
int B; float L; int S;
while (N--){
cin >> B >> L >> S;
if (L >= 2.0 && S >= 17){
ans += M[B];
}
}
cout << ans;
return 0;
}
문제에서 주어진 그대로 구현하면 된다.
// 34553번 알파벳 점수 계산기
// 구현, 문자열
#include <iostream>
using namespace std;
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl '\n'
int main(void){
fastio
string S; cin >> S;
int ans = 1;
int add = 1;
for (int i = 1; i < S.size(); ++i){
if (S[i] > S[i-1]){
add++;
} else {
add = 1;
}
ans += add;
}
cout << ans;
return 0;
}
약수의 개수가 정확히 $2$개가 되는 수는 소수이다.
두 자연수의 곱이 소수라면, 두 자연수는 각각 $1$과 자기 자신이 된다.
따라서, $B$는 소수, $A$는 $1$이 되어야 하며, $B-A = N \rightarrow B = N+1$.
즉, $N+1$이 소수라면 $N+1$과 $1$을 출력하고 그게 아니라면 $0$을 출력하면 된다.
// 34554번 특수한 정수 쌍
// 소수 판정
#include <iostream>
using namespace std;
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl '\n'
bool is_prime(int N){
if (N == 1) return false;
for (int i = 2; i*i <= N; ++i){
if (N % i == 0){
return false;
}
}
return true;
}
void solve(void){
int N; cin >> N;
if (is_prime(N+1)){
cout << 1 << endl << 1 << ' ' << N+1 << endl;
} else {
cout << 0 << endl;
}
return;
}
int main(void){
fastio
int T; cin >> T;
while (T--){
solve();
}
return 0;
}
인접한 두 수의 차가 오름차순이 되도록 나열하면 된다.
배열해야하는 수가 $N$개라면, $1, \ 2, \ 3, \cdots, N-1$이 인접한 수의 차이가 되도록 나열해야 한다.
따라서, 수의 중간부터 시작하여 $1$을 빼고, $2$를 더하고, $3$을 빼고, ... 그런 식으로 수열을 구성하면 된다.
// 34555번 INU 순열
// 애드혹, 해 구성하기
/*
접근 방법:
숫자의 절반 오름차순
숫자의 절반 내림차순
교대로 배열
3 2 4 1
3 2 4 1 5
4 3 5 2 6 1
...
*/
#include <iostream>
using namespace std;
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl '\n'
int main(void){
fastio
int N; cin >> N;
int odd = N/2 + 1, even = N/2;
for (int i = 0; i < N; ++i){
if (i % 2 == 0){
cout << odd << ' ';
odd++;
} else {
cout << even << ' ';
even--;
}
}
return 0;
}
한쪽 성별은 고정하고, 다른 성별 사람들의 순서를 섞은 다음에 매칭하면 된다.
즉, 순열을 구하는 문제로 바뀌게 되는데, 이는 백트래킹으로 쉽게 구할 수 있다.
가지치기를 할 수 있는데, 남은 사람들이 모두 4점을 얻는다고 해도 최대 점수를 갱신할 수 없다면 리턴하는 식으로 잘라낼 수 있다.
// 34556번 MBTI 소개팅
// 백트래킹, 완전 탐색
#include <iostream>
#include <vector>
using namespace std;
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl '\n'
int MAX = 0;
int visited[11] = {0,};
int N;
vector<string> man_MBTI(10);
vector<string> woman_MBTI(10);
int score = 0;
int compare(string& a, string& b){
int ret = 0;
for (int i = 0; i < 4; ++i){
if (a[i] != b[i]){
ret++;
}
}
return ret;
}
void dfs(int depth){
if (score + 4*(N-depth) < MAX){
return;
}
if (depth == N){
MAX = max(score, MAX);
return;
}
for (int i = 0; i < N; ++i){
if (!visited[i]){
visited[i] = 1;
score += compare(woman_MBTI[depth], man_MBTI[i]);
dfs(depth+1);
score -= compare(woman_MBTI[depth], man_MBTI[i]);
visited[i] = 0;
}
}
return;
}
int main(void){
fastio
cin >> N;
for (int i = 0; i < N; ++i){
cin >> man_MBTI[i];
}
for (int i = 0; i < N; ++i){
cin >> woman_MBTI[i];
}
dfs(0);
cout << MAX << endl;
return 0;
}
사용자가 누른 키에 대해서 각 이벤트가 부여되는데, 'W', 'A', 'S', 'D' 순으로 우선적으로 일치하는 이벤트를 처리해야 한다.
이를 구현하기 위해 현재 입력된 키와 이전에 입력된 키의 우선 순위를 비교했다. 두 키 중 우선순위가 높은 쪽 먼저 이벤트를 처리하도록 구현했다.
// 34557번 횃불이의 모험
// 구현
/*
접근 방법:
*/
#include <iostream>
#include <vector>
using namespace std;
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl '\n'
int dr[4] = {-1, 0, 1, 0}, dc[4] = {0, -1, 0, 1};
int find_idx(char ch){
string wasd = "WASD";
for (int i = 0; i < 4; ++i){
if (wasd[i] == ch){
return i;
}
}
return -1;
}
int main(void){
fastio
int N, M; cin >> N >> M;
vector<vector<int>> MAP(N, vector<int>(N, 0));
int r, c;
for (int i = 0; i < N; ++i){
for (int j = 0; j < N; ++j){
cin >> MAP[i][j];
if (MAP[i][j] == 2){
r = i; c = j;
MAP[i][j] = 0;
}
}
}
vector<string> keyevent(4);
for (int i = 0; i < 4; ++i){
cin >> keyevent[i];
}
string order; cin >> order;
char before_key = ' ';
for (int i = 0; i < M; ++i){
char now_key = order[i];
string now_event = "", before_event = "";
if (before_key == now_key){
now_event = "Stay";
} else {
now_event = "Down";
before_event = "Up";
}
int j = find_idx(now_key);
int k = find_idx(before_key);
if (j < k){
if (j != -1 && keyevent[j] == now_event){
int nr = r+dr[j], nc = c+dc[j];
if (0 <= nr && nr < N && 0 <= nc && nc < N && MAP[nr][nc] == 0){
r = nr, c = nc;
}
}
if (k != -1 && keyevent[k] == before_event){
int nr = r+dr[k], nc = c+dc[k];
if (0 <= nr && nr < N && 0 <= nc && nc < N && MAP[nr][nc] == 0){
r = nr, c = nc;
}
}
} else {
if (k != -1 && keyevent[k] == before_event){
int nr = r+dr[k], nc = c+dc[k];
if (0 <= nr && nr < N && 0 <= nc && nc < N && MAP[nr][nc] == 0){
r = nr, c = nc;
}
}
if (j != -1 && keyevent[j] == now_event){
int nr = r+dr[j], nc = c+dc[j];
if (0 <= nr && nr < N && 0 <= nc && nc < N && MAP[nr][nc] == 0){
r = nr, c = nc;
}
}
}
before_key = now_key;
}
cout << r+1 << ' ' << c+1;
return 0;
}
쿼리의 개수가 $100 \ 000$개이고, 구간의 범위가 최대 $10^6$이기 때문에, 나이브하게 모든 범위의 수에 대해서 소수 판정을 진행하는 풀이는 $\mathcal{O}(100 \ 000 \cdot 10^6 \cdot \sqrt{n})$의 시간복잡도가 소요된다.
따라서, 일단 에라토스테네스의 체를 사용하여 $10^6$까지의 모든 소수를 구한 후, 해당 소수들만 저장한다.
이후 각 쿼리 $[a_i, b_i]$마다 $b_i$가 소수 리스트에 어디에 위치할 지, $a_i$가 소수 리스트에 어디에 위치할 지를 각각 lower_bound와 upper_bound를 통해 $\mathcal{O}(\log N)$으로 구한다. ($N$은 $10^6$까지의 소수의 개수)
// 34558번 Prime Median
// 에라토스테네스의 체, 이분 탐색
/*
접근 방법:
에테체로 구하고 쿼리마다 이분 탐색 갈기기
*/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl '\n'
int sieve[1'000'001] = {0,};
int main(void){
fastio
sieve[0] = 1; sieve[1] = 1;
for (int i = 2; i*i < 1'000'001; ++i){
if (sieve[i] == 0){
for (int j = i*i; j < 1'000'001; j += i){
sieve[j] = 1;
}
}
}
vector<int> primes;
for (int i = 0; i < 1'000'001; ++i){
if (sieve[i] == 0){
primes.push_back(i);
}
}
int N; cin >> N;
int a, b;
while (N--){
cin >> a >> b;
int p = distance(primes.begin(), lower_bound(primes.begin(), primes.end(), a));
int q = distance(primes.begin(), upper_bound(primes.begin(), primes.end(), b));
int cnt = q-p;
if (cnt % 2 == 0 || cnt < 0){
cout << -1 << endl;
} else {
cout << primes[(p+q)/2] << endl;
}
}
return 0;
}
치즈 문제의 아이디어를 사용할 수 있다.
0에서부터 시작하여 지도 테두리로 이동한다고 생각하지 않고, 지도 테두리에서 역으로 출발하여 도달할 수 없다면 건물 내부라고 생각하면 된다.
그래서 먼저 BFS를 진행하여 건물을 모두 1로 표현한다.
고객의 수 $Q = 10^6$이기 때문에, 각 쿼리마다 나이브하게 주어진 범위에서 $1$의 개수를 세는 건 시간초과를 받는다.
따라서, $2$차원 누적 합을 이용하여, 각 쿼리를 $\mathcal{O}(1)$로 처리하면 된다.
// 34559번 건물 측량
// BFS, 누적 합
/*
접근 방법:
테두리에서 BFS 돌려서 건물을 모두 1로 표시
이후 2차원 누적합 때린다.
*/
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl '\n'
int dr[4] = {-1, 1, 0, 0}, dc[4] = {0, 0, -1, 1};
void BFS(vector<vector<int>>& MAP){
int N = MAP.size(), M = MAP[0].size();
vector<vector<int>> visited(N, vector<int>(M, 0));
// 테두리 담기
queue<pair<int, int>> Q;
for (int i = 0; i < N; ++i){
if (i == 0 || i == N-1){
for (int j = 0; j < M; ++j){
if (MAP[i][j] == 0){
Q.push({i, j});
visited[i][j] = 1;
}
}
} else {
if (M == 1){
if (MAP[i][0] == 0){
Q.push({i, 0});
visited[i][0] = 1;
}
} else {
if (MAP[i][0] == 0){
Q.push({i, 0});
visited[i][0] = 1;
}
if (MAP[i][M-1] == 0){
Q.push({i, M-1});
visited[i][M-1] = 1;
}
}
}
}
// BFS 수행
while (!Q.empty()){
int r = Q.front().first, c = Q.front().second;
Q.pop();
for (int i = 0; i < 4; ++i){
int nr = r+dr[i], nc = c+dc[i];
if (0 <= nr && nr < N && 0 <= nc && nc < M){
if (MAP[nr][nc] == 0 && visited[nr][nc] == 0){
visited[nr][nc] = 1;
Q.push({nr, nc});
}
}
}
}
// visited되지 않은 모든 MAP의 원소들 바꾸기
for (int i = 0; i < N; ++i){
for (int j = 0; j < M; ++j){
if (visited[i][j] == 0){
MAP[i][j] = 1;
}
}
}
return;
}
vector<vector<int>> accumsum(vector<vector<int>>& MAP){
int N = MAP.size(), M = MAP[0].size();
vector<vector<int>> acc(N+1, vector<int>(M+1, 0));
for (int i = 0; i < N; ++i){
for (int j = 0; j < M; ++j){
acc[i+1][j+1] = acc[i][j+1] + acc[i+1][j] - acc[i][j] + MAP[i][j];
}
}
return acc;
}
int main(void){
fastio;
int N, M; cin >> N >> M;
vector<vector<int>> MAP(N, vector<int>(M));
char ch;
for (int i = 0; i < N; ++i){
for (int j = 0; j < M; ++j){
cin >> ch;
MAP[i][j] = ch-'0';
}
}
BFS(MAP);
vector<vector<int>> A = accumsum(MAP);
int Q; cin >> Q;
int r1, c1, r2, c2;
while (Q--){
cin >> r1 >> c1 >> r2 >> c2;
int P = A[r2][c2] - A[r1-1][c2] - A[r2][c1-1] + A[r1-1][c1-1];
if (P){
cout << "No " << P << endl;
} else {
cout << "Yes" << endl;
}
}
return 0;
}
전형적인 위상 정렬 문제다.
하나의 캐릭터를 하나의 정점으로 생각하고, 모든 정점 쌍에 대해서 승/패 여부를 따져주어 그래프의 간선을 만들어준다.
이때 간선을 만들어줌과 동시에 indegree값 또한 구해준다.
이후 위상 정렬을 실시한다.
indegree가 0인 정점을 계속해서 뜯어내는데, 뜯어내는게 불가능하다면 Paradoxe Absurdo출력하면 된다.
시간 복잡도는 $\mathcal{O}(N^2)$가 된다.
// 34560번 브레인롯 챔피언십
// 위상 정렬
/*
접근 방법:
모든 정점들에 대해서 승패 여부를 따진 뒤 간선 만들기
이후 위상정렬
위상 정렬 불가능 하면
Paradoxe Absurdo 출력
궁극의 승리자가 여러 개라면 이름순으로 출력합니다.
*/
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl '\n'
int main(void){
fastio
int N; cin >> N; // 캐릭터의 수
vector<int> P(N), A(N), S(N);
vector<string> name(N);
for (int i = 0; i < N; ++i){
cin >> name[i] >> P[i] >> A[i] >> S[i];
}
// 그래프 구성, 진입차수 설정
vector<vector<int>> G(N);
vector<int> indegree(N, 0);
for (int i = 0; i < N; ++i){
for (int j = i+1; j < N; ++j){
int win_i = 0, win_j = 0;
if (P[i] >= P[j]) ++win_i;
if (P[j] >= P[i]) ++win_j;
if (A[i] >= A[j]) ++win_i;
if (A[j] >= A[i]) ++win_j;
if (S[i] >= S[j]) ++win_i;
if (S[j] >= S[i]) ++win_j;
if (win_i > win_j){
G[i].push_back(j);
indegree[j]++;
}
if (win_j > win_i){
G[j].push_back(i);
indegree[i]++;
}
}
}
// 진입 차수 0인 노드들 찾기
vector<string> ans;
queue<int> Q;
for (int i = 0; i < N; ++i){
if (indegree[i] == 0){
Q.push(i);
ans.push_back(name[i]);
}
}
// 위상 정렬 실시
vector<int> order;
while (!Q.empty()){
int now = Q.front();
order.push_back(now);
Q.pop();
for (int near : G[now]){
indegree[near]--;
if (indegree[near] == 0){
Q.push(near);
}
}
}
if (order.size() != N){
cout << "Paradoxe Absurdo" << endl;
} else {
sort(ans.begin(), ans.end());
for (string S : ans){
cout << S << endl;
}
}
return 0;
}
$N$의 제한이 $300 \ 000$이고 쿼리의 개수가 최대 $500 \ 000$이기 때문에, 1번 쿼리(업데이트 쿼리)를 $\mathcal{O}(N)$에 처리하면 시간초과를 받는다.
업데이트 쿼리를 최대한 빠르게 하는 것이 관건이고, 다음과 같은 아이디어로부터 빠르게 수행할 수 있다.
어떤 하나의 값을 "모두" 선택하여 "모두" 바꾸면, 수열에서 점점 같은 값을 가지는 원소가 많아진다.
즉, 만약 $y$값이 이미 존재하고 $x$값에 해당하는 원소들을 모두 $y$값으로 변경한다면, $y$값을 가지는 원소들의 개수가 늘어난다는 뜻이다.
따라서, 어떤 특정한 값을 가지고 있는 원소들을 서로 "묶어"준다는 점에서 "분리 집합"을 생각할 수 있다.
이때 우리는 조회 쿼리를 위해 $i \rightarrow A_i$매핑(mapping1) 하나와 업데이트 쿼리를 위해 $A_i \rightarrow i$매핑(mapping2) 하나를 만든다.
당연히 이때의 인덱스 매핑은 해당 집합의 대표 노드의 인덱스이다.
$1 \ x \ y$가 들어올 때, 만약 $x = y$이거나 $x$가 mapping2에 존재하지 않는다면 무시한다.
그 외의 경우, 2개의 케이스로 나눌 수 있다.
1. $y$가 mapping2에 존재하는 경우.
이때, $\text{mapping2}[x] = i, \text{mapping2}[y] = j$ 두 노드를 merge한다.
이후 대표노드를 $k$라고 하면 $\text{mapping2}[y] = k, \text{mapping1}[k] = y$를 넣어주고, 기존의 $x, y$에 매핑된 것들은 제거해준다.
2. $y$가 mapping2에 존재하지 않은 경우.
이때는 merge할 필요가 없으므로, 그냥 mapping1의 값만 변경해주면 된다.
조회 쿼리를 수행할 때는 mapping1을 이용하면 된다.
따라서, 업데이트를 거의 $\mathcal{O}(1)$에 가깝게 수행할 수 있다.
// 34561번 수열과 쿼리 2025
// 분리 집합, 집합과 맵
/*
문제 :
길이가 $N$이고 정수로 구성된 수열 $A_1$, $A_2$, $\dots$, $A_N$이 주어집니다.
이때, 다음 쿼리를 수행하는 프로그램을 작성해 주세요.
$1$ $x$ $y$: 수열에서 $x$인 값을 모두 선택하여, $y$로 바꿉니다.
$2$ $z$: $A_z$를 출력합니다.
접근 방법:
기본적으로 분리 집합 초기화 해주고, 같은 수가 주어질 때 merge하는 식으로 ㄱㄱ
그리고
mapping1 = 대표 인덱스 i -> A_i
mapping2 = A_i -> 대표 인덱스 i
로 매핑 2개를 만들어준다...
1 x y
1-1. 만약 y가 mapping2에 있다면
mapping2[x] = idx1와 mapping2[y] = idx2를 merge
-> idx1과 idx2 중 대표가 되는 노드를 idx라고 하자.
mapping2[x] 삭제, mapping2[y] = idx로 변경
mapping1[idx1] 삭제, mapping1[idx2] 삭제, mapping1[idx] = y 추가
1-2. 만약 y가 mapping2에 없다면
mapping2[x] = idx를 찾고,
mapping1[idx] = y로 변경 -> mapping2[x]를 삭제 후 mapping2[y] = idx로 재할당
2 z
find(z) = idx
mapping1[idx] 출력
*/
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl '\n'
int _find(vector<int>& parent, int node){
if (parent[node] != node){
parent[node] = _find(parent, parent[node]);
}
return parent[node];
}
void _merge(vector<int>& parent, vector<int>& size, int node1, int node2){
int p1 = _find(parent, node1);
int p2 = _find(parent, node2);
if (p1 == p2) return;
if (size[p1] > size[p2]){
size[p1] += size[p2];
parent[p2] = p1;
} else {
size[p2] += size[p1];
parent[p1] = p2;
}
return;
}
int main(void){
fastio
int N; cin >> N; // 수열의 크기
// init
vector<int> parent(N);
vector<int> size(N, 1);
for (int i = 0; i < N; ++i){
parent[i] = i;
}
unordered_map<int, int> mapping1, mapping2;
vector<int> A(N);
for (int i = 0; i < N; ++i){
cin >> A[i];
if (mapping2.find(A[i]) != mapping2.end()){
int j = mapping2[A[i]];
mapping1.erase(j);
_merge(parent, size, i, j);
int rep = _find(parent, i);
mapping2[A[i]] = rep;
mapping1[rep] = A[i];
} else {
mapping2[A[i]] = i;
mapping1[i] = A[i];
}
}
int M; cin >> M; // 쿼리의 개수
int query, x, y, z;
while (M--){
cin >> query;
if (query == 1){
cin >> x >> y;
if (x == y) continue;
if (mapping2.find(x) == mapping2.end()) continue;
if (mapping2.find(y) != mapping2.end()){
int node1 = mapping2[x], node2 = mapping2[y];
_merge(parent, size, node1, node2);
int rep = _find(parent, node1);
mapping2.erase(x);
mapping2[y] = rep;
mapping1.erase(node1); mapping1.erase(node2);
mapping1[rep] = y;
} else {
int node1 = mapping2[x];
mapping1[node1] = y;
mapping2.erase(x); mapping2[y] = node1;
}
} else {
cin >> z;
z--;
int rep = _find(parent, z);
cout << mapping1[rep] << endl;
}
}
return 0;
}
1번에서 시작하여 1번으로 "돌아온다"는 점에서 TSP를 생각할 수 있다.
다만 기존 TSP와 다른 점은 중복 정점의 방문을 허용한다는 것인데, 이것을 처리하는 아이디어가 까다롭다.
플로이드-워셜을 통해 직접적으로 이어지지 않은 두 정점 사이에 "간접 간선"을 만들어준다.
이러면 기존 TSP를 활용할 수 있다. 다만, DP 정의식이 약간 변경된다.
실제로 없는 간선을 만들어준 것이기 때문에 만약 $3$개의 정점을 지난 상태에서 "간접 간선"을 통해 다른 정점으로 이동했다면, 아직 방문하지 않은 정점 하나로 움직이는 것이 아니라, 내가 방문하지 않았던 다른 정점을 거쳐서 이동할 수도 있기 때문이다.
따라서 TSP[visited][u] = 적어도 visited의 정점을 방문했고(더 많이 방문했을 수도 있음), 정점 u에 있을 때의 최소 값이라고 정의가 된다.
이후 $i^2$점을 얻기 위한 최소 비용은 $\min(TSP[visited][u] + W[u][0])$로 정의가 되며 $visited$의 비트 개수 $-1$이 $i$로 정의된다.
$K$의 체력이 있을 경우 여러 번 턴을 진행하여 "최대 점수"를 얻고자 하는 것이므로, 냅색 DP를 이용하여 값을 구하면 된다.
// 34562번 터치 앤 리턴
// 최단 경로, 플로이드 워셜, TSP, Bitfield DP, 배낭 문제
/*
접근 방법:
두 지점을 잇는 통로가 여러개 일 경우 -> 가장 작은거 하나만 남긴다
그렇게 만들어진 인접행렬을 토대로 TSP를 돌린다.
+) 인접행렬을 그대로 쓰는게 아니라 플로이드 워셜 돌리자...
DP[visited][i]인데,
i에서 1번으로 돌아오는 최단 경로를 더해주면 visited된 노드들을 방문한 최소 순환 사이클이 나온다.
(visited.bit_count()-1)**2 = value
DP[visited][i] + min_dist(i, 1) = cost
해당 value와 cost쌍을 토대로 냅색을 돌린다.
*/
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl '\n'
#define INF 1'000'000'000
int main(void){
fastio
// 지점의 수, 통로의 수, 용준이의 체력
int N, M, K; cin >> N >> M >> K;
// 인접 행렬
vector<vector<int>> G(N, vector<int>(N, INF));
// 간선 추가
int a, b, c;
for (int i = 0; i < M; ++i){
cin >> a >> b >> c;
a--; b--;
if (G[a][b] > c) G[a][b] = c;
if (G[b][a] > c) G[b][a] = c;
}
// 플로이드 워셜 돌리기
for (int m = 1; m < N; ++m){
for (int s = 0; s < N; ++s){
for (int e = 0; e < N; ++e){
G[s][e] = min(G[s][e], G[s][m] + G[m][e]);
}
}
}
// TSP돌리기
vector<vector<int>> tsp(1 << N, vector<int>(N, INF));
tsp[1][0] = 0;
for (int visited = 1; visited < (1 << N); ++visited){
if ((visited & 1) == 0) continue;
for (int u = 0; u < N; ++u){
if ((visited & (1 << u)) == 0) continue; // 정점 u는 방문한 정점.
for (int v = 0; v < N; ++v){
if (visited & (1 << v)) continue; // 정점 v는 방문하지 않은 정점.
tsp[visited | (1 << v)][v] = min(tsp[visited | (1 << v)][v], tsp[visited][u] + G[u][v]);
}
}
}
// TSP 결과와 floyd_warshall결과를 합쳐서 순환 결과 찾기
vector<int> cost_arr(N, INF); // cost_arr[i] = i*i점을 얻기 위한 최소 cost
for (int visited = 1; visited < (1 << N); ++visited){
if ((visited & 1) == 0) continue;
int i = __builtin_popcount(visited);
i--;
for (int u = 0; u < N; ++u){
if (visited & (1 << u)){
int min_cost = tsp[visited][u] + G[u][0];
if (cost_arr[i] > min_cost){
cost_arr[i] = min_cost;
}
}
}
}
// 냅색 돌리기.
int ans = 0;
vector<int> knapsack(K+1, 0);
for (int i = 0; i <= K; ++i){
for (int j = 0; j < N; ++j){
if (i >= cost_arr[j]){
knapsack[i] = max(knapsack[i], knapsack[i-cost_arr[j]] + j*j);
}
}
ans = max(ans, knapsack[i]);
}
cout << ans << endl;
return 0;
}
반응형
'알고리즘 > 백준 문제 풀이' 카테고리의 다른 글
| [C++] 24558번 Downsizing (0) | 2025.10.21 |
|---|---|
| [C++] 34041번 회전체와 쿼리 (0) | 2025.10.20 |
| [C++] 11585번 속타는 저녁 메뉴 (추후 보강 예정) (0) | 2025.10.06 |
| [C++] 1238번 파티 (0) | 2025.10.06 |
| [C++] 17999번 Maze Connect (0) | 2025.10.06 |
