4-C 어느 부분이 틀렸는지 모르겠습니다.
https://www.acmicpc.net/source/share/e76dff0067f048f28c1a105de7d81014
강의를 봤는데도 코드가 왜 틀린건지 잘 이해가 안되네요.
테케는 통과했는데, 2%에서 틀립니다. 리뷰 부탁드립니다!
답변 1
1
안녕하세요 곰다님 ㅎㅎ
전체적인 로직은 너무나 잘 짜쎴네요 ㅎㅎ
다만, 해당 코드를 제가 다듬어봤습니다.
이렇게 하시면 됩니다. :)
참고부탁드립니다.
#include <bits/stdc++.h>
using namespace std;
int iN, iMin = INT_MAX;
int Population[11];
vector<int> Adj[11];
bool Visited[11];
void Solve(int node, int check, int &able)
{
for (int adj : Adj[node])
{
if ((check & (1 << adj)) && !Visited[adj])
{
Visited[adj] = true;
able |= (1 << adj);
Solve(adj, check, able);
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> iN;
for (int i = 1; i <= iN; ++i)
{
cin >> Population[i];
}
for (int i = 1; i <= iN; ++i)
{
int iTemp, iDest;
cin >> iTemp;
while (iTemp--)
{
cin >> iDest;
Adj[i].push_back(iDest);
Adj[iDest].push_back(i);
// 양방향간선을 정확히 만들어야 합니다.
}
}
for (int i = 1; i < (1 << iN); ++i)
{
int iArea1 = 0, iArea2 = 0;
int iStart1 = 0, iStart2 = 0;
int iSum1 = 0, iSum2 = 0;
for (int j = 0; j < iN; ++j)
{
if (i & (1 << j))
{
iSum1 += Population[j + 1];
iArea1 |= (1 << (j + 1));
if (iStart1 == 0)
{
iStart1 = j + 1;
}
}
else
{
iSum2 += Population[j + 1];
iArea2 |= (1 << (j + 1));
if (iStart2 == 0)
{
iStart2 = j + 1;
}
}
}
if (iStart1 == 0 || iStart2 == 0)
{
continue;
}
if (iMin > abs(iSum1 - iSum2))
{
int iAble = 0;
memset(Visited, 0, sizeof(Visited));
Visited[iStart1] = true;
iAble |= (1 << iStart1);
Solve(iStart1, iArea1, iAble);
if (iArea1 != iAble)
{
continue;
}
iAble = 0;
memset(Visited, 0, sizeof(Visited));
Visited[iStart2] = true;
iAble |= (1 << iStart2);
Solve(iStart2, iArea2, iAble);
if (iArea2 != iAble)
{
continue;
}
iMin = abs(iSum1 - iSum2);
}
}
if (iMin == INT_MAX)
{
cout << -1;
}
else
{
cout << iMin;
}
return 0;
}
또 질문 있으시면 언제든지 질문 부탁드립니다.
좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.
0
답변 감사합니다 선생님! 몇 가지 질문하고 싶습니다.
1. 양방향 간선은 입력단계에서 자연스럽게 만들어지는 거 아닌가요?
for (int i = 1; i <= iN; ++i)
{
int iTemp, iDest;
cin >> iTemp;
while (iTemp--)
{
cin >> iDest;
Adj[i].push_back(iDest);
Adj[iDest].push_back(i);
// 양방향간선을 정확히 만들어야 합니다.
}
}'단방향 간선이 있을 수 있다' 라면 틀린 이유가 납득되는데, 문제 및 작성하신 코드를 보니 주어지는 간선은 모두 양방향 간선으로 보입니다. 예를 들어 3과 5가 연결되어 있다면 for문에서 i가 3일 때 Adj[5].push_back(3); 이 부분은 필요없이 i가 5일 때 처리되는거 아닌가요?
2. 저는 int Adj[11]; 형태로 인접 리스트도 비트마스킹으로 나타내려 했는데 이러면 인접한 수들만 순회가 아니라 1 ~ iN 중 켜져있는 비트를 찾아서 순회라서 바꿔서 사용하신건가요?
3. 문제와 별개로 비트마스킹을 사용해야겠다라고 떠올리시는 단계가 어느 부분인지 궁금합니다. 이전 강의들에서 말씀하신 완탐 - Bfs,Dfs - 그리디 순의 단계처럼 따로 생각하시는 포인트가 있는지 궁금하네요. (4-A에서 비트마스킹 쉽네!했다가 4-B에서 털려서 알고 가야 편하겠다는 생각이 들어 질문합니다 ㅎ.. ㅠ)
1
안녕하세요 곰다님 ㅎㅎ
Q1 >> 아 네 맞습니다. 이 문제같은 경우 그렇게 하셔도 됩니다. 제가 착각했습니다. ㅠ
Q2 >> 질문이 좀 모호한데요.
저는 int Adj[11]; 형태로 인접 리스트도 비트마스킹으로 나타내려 해도 될까요? 라는 질문인가요? -> 그러셔도 됩니다. 다만 저는 인접리스트가 더 편하다고 생각합니다. 굳이 모든 정점을 탐색하지 않아도 되니까요.
Q3. >>
음... 여러개의 경우의 수 -> 조합을 좀 더 깔끔하게 풀고자 해서 -> 비트마스킹을 한 것이라고 보면 됩니다. nC1, nC2, nC3 ... 의 모든 경우의 수 ? -> 깔끔하게 비트마스킹으로 시도해볼까? -> 어? 이거 문제범위가 어느정도지? -> N이 10이네..?30이하면 비트마스킹으로 가능하다고 했지? -> 고고
이런 플로우입니다. ㅎㅎ
감사합니다.
코딩살구클럽 가입이 안됩니다.
0
15
0
살구 클럽에 대한 질문있습ㄴ디ㅏ
0
27
1
교안 158페이지 문의드립니다
0
34
2
코딩살구클럽 관련 건의사항
0
71
1
코살에 19942 다이어트 문제에 N의 범위가 빠져있슴니다
0
33
1
진행 방법 질문드립니다!
0
65
2
2-I) 왜 이 문제가 그래프이론 카테고리에 있는지 잘 모르겠습니다.
0
60
2
2주차 개념#12 트리 순회
0
29
2
백준사이트가 종료된다고 합니다.
0
291
2
백준 서비스 종료
9
904
1
sk 하이닉스 코테 대비
0
373
2
3-G 최댓값 질문
0
52
1
모듈러 연산 값이 10이 아닌 경우도 있지 않나요?
0
84
2
3-I 코드 질문드립니다.
0
63
2
3-N 질문 있습니다.
0
68
2
학습방법
0
103
2
4-H 질문 있습니다 (코드 리뷰)
0
67
2
코딩테스트 어디까지 준비해야 하는지 질문이 있습니다.
0
174
2
2-O 반례가 무엇일지 어떤 부분이 틀렸는지 잘 모르겠습니다.
0
70
2
2주차 개념 #4-2. 인접행렬 질문있습니다.
0
65
2
1-A 문제풀이 후 궁금한 점이 생겨서 질문드립니다.
0
52
2
조합 재귀 풀이 확인 해주시면 감사하겠습니다.
0
69
2
함수별 시간복잡도
0
75
2
3-h 질문입니다.
0
50
1