반갑습니다!

2887번: 행성 터널 boj.kr 풀이 문제를 읽어보면 MST를 만들어주면 해결할 수 있을거라는 생각이 든다. 그런데 일반적인 문제와 달리 간선의 길이가 주어져있지 않고 min(|xA-xB|, |yA-yB|, |zA-zB|)라는 조건만 나와있다. 이를 위해서 모든 접점 간의 거리를 구해 MST를 만들려고 하면 메모리 초과가 발생한다. 그렇기 때문에 다른 방식을 생각해야 한다. 사실 이 문제는 모든 접점 간의 거리를 구할 필요가 없다. 결국 MST를 만들어야하므로 각 접점 간의 최소 거리가 필요하다. 접점 간의 최소 거리라는 것은 결국 min(|xA-xB|, |yA-yB|, |zA-zB|)을 통해 계산한 거리이다. 이 것을 다시 생각해보면 두 접점 사이에 x값을 기준으로 한 간선, y값을 기준으로 한 간..

1647번: 도시 분할 계획 boj.kr 풀이 이 문제는 최소한의 비용으로 두 마을을 만들어야하는데, 결국 1개의 최소 스패닝 트리를 만들고 그 중에 가장 큰 간선을 제거해주면 최소한의 비용으로 2개의 마을을 만든 것과 같다. 크루스칼 알고리즘을 사용해서 최소 스패닝 트리를 만들어서 해결하였다. 코드 C++ #include #include #include using namespace std; int n, m; vector edges; vector root; int find(int v) { if (root[v] != v) root[v] = find(root[v]); return root[v]; } void merge(int a, int b) { a = find(a); b = find(b); if (a < ..

15809번: 전국시대 boj.kr 풀이 이 문제는 유니온 파인드(서로소 집합)를 사용해서 해결할 수 있는 문제이다. 두 나라가 동맹과 전쟁을 수행할 때마다 나라가 합쳐지는데, 이 때 병력을 처리하는 부분만 신경써주면 어렵지 않게 해결할 수 있다. 전쟁을 했는데 두 나라의 병력이 같은 경우에는 부모를 0으로 해줌으로서 정답을 출력할 때 제외할 수 있도록 처리했다. 코드 C++ #include #include #include #include using namespace std; int n, m; vector root, power; int find(int x) { if (root[x] != x) root[x] = find(root[x]); return root[x]; } void merge(int a, in..

2153번: 소수 단어 boj.kr 풀이 에라토스테네스의 체를 사용해 1부터 최대값인 20 * 52 까지의 범위에 있는 소수를 모두 구한 뒤, 입력 들어온 문자열을 숫자로 바꿔서 소수 여부를 확인했다. 코드 C++ #include using namespace std; const int MAX = 20 * 52; int main() { bool arr[MAX + 1]; for (int i = 1; i

3986번: 좋은 단어 boj.kr 풀이 괄호 짝을 맞추듯 A는 A끼리, B는 B끼리 짝을 맞춰주면 된다. 문자열을 모두 체크하고도 스택에 값이 남아있으면 좋은 단어가 아니게 된다. 코드 C++ #include #include using namespace std; d iasdfnt main() { int n; cin >> n; int answer = 0; while (n--) { string s; cin >> s; stack st; for (char c : s) { if (st.empty() || st.top() != c) st.push(c); else st.pop(); } if (st.empty()) answer++; } cout