Approach 전형적인 LCA 문제 Code #include #define fastio cin.tie(0)->sync_with_stdio(0) using namespace std; using ll = long long; using pii = pair; int move_x[4] = {-1, 1, 0, 0}; int move_y[4] = {0, 0, -1, 1}; const int MAX = 18; vector adj[100001]; int parent[100001][18]; int depth[100001]; bool visited[100001]; void dfs(int cur, int cur_depth){ visited[cur] = 1; depth[cur] = cur_depth; for(auto &p :..

Approach 정해진 출발점을 기준으로 최단거리가 m보다 작으면 방문할 수 있는 정점이라는 아이디어를 파악했으면 모든 정점을 출발점으로 설정하고, 다익스트라를 통해 최단거리가 m보다 더 작은 모든 정점에 속한 아이템의 수를 다 더해준 뒤 그 중 최댓값을 출력해주면 된다. Code #include #define fastio cin.tie(0)->sync_with_stdio(0) using namespace std; typedef long long ll; typedef pair pii; int move_x[4] = {-1, 1, 0, 0}; int move_y[4] = {0, 0, -1, 1}; const int INF = 1000000000; //ElogV * V int main() { fastio; i..

Approach 다익스트라를 돌리되, parent 배열을 따로 잡아줘서 역추적해주면 된다. Code #include #define fastio cin.tie(0)->sync_with_stdio(0) using namespace std; typedef long long ll; typedef pair pii; int move_x[4] = {-1, 1, 0, 0}; int move_y[4] = {0, 0, -1, 1}; const int INF = 200000000; int main() { fastio; int n, m; cin >> n >> m; vector edge[n]; for(int i = 0; i > a >> b >> c; edge[a - 1].pu..

Approach 잘 생각해보면, 비용 단위로 최단거리를 구해주면 된다. https://viyoung.tistory.com/369 문제와 유사하다. Code #include #define fastio cin.tie(0)->sync_with_stdio(0) using namespace std; typedef long long ll; typedef pair pii; typedef tuple tiii; int move_x[4] = {-1, 1, 0, 0}; int move_y[4] = {0, 0, -1, 1}; const int INF = 100000000; int main() { fastio; int t; cin >> t; while(t--){ int n, m, k; cin >> n >> m >> k; vec..

Approach 부분수열은 비트마스킹을 활용하여 쉽게 처리할 수 있다. 각각의 정수가 들어갈 지 안들어갈 지 선택할 수 있는 상황이므로, 총 가짓수는 $2^N$개이다. 잘 생각해보면, 0과 1을 활용핵서 들어갈 지 안들어갈 지 결정할 수 있고 이는 이진수를 활용해서 처리할 수 있다. 즉, N개의 정수를 활용해서 만들 수 있는 개수는 N개의 비트를 황룡해서 만들 수 있는 수와 완벽하게 동일하다. 따라서 1부터 $1 sync_with_stdio(0) using namespace std; typedef long long ll; typedef pair pii; int move_x[4] = {-1, 1, 0, 0}; int move_y[4] = {0, 0, -1, 1}; int main() { fastio; in..

Approach 수능 수학 문제처럼 높이를 고정시켜둔 상태에서의 cost를 구하는 것은 크게 어렵지 않다. 추가적으로 나올 수 있는 높이는 0 ~ 256까지이므로, 연산이 최대로 많아봐야 500 * 500 * 256이고 이는 1억 미만이다. 따라서 Brute force적으로 접근해도 시간 안에 통과할 수 있다. Code #include #define fastio cin.tie(0)->sync_with_stdio(0) using namespace std; typedef long long ll; typedef pair pii; int move_x[4] = {-1, 1, 0, 0}; int move_y[4] = {0, 0, -1, 1}; int main() { int n, m, b; cin >> n >> m ..

Approach 잘 생각해보면 3과 2는 서로소이므로, 배타적으로만 존재가능하다. 예를 들어 v[i]라는 숫자가 존재한다고 했을 때, v[i] / 3이 존재하거나 v[i] * 2만 존재해야 한다. 왜냐하면, 3과 2는 서로소이기 때문에 3으로 나눈 것을 아무리 2를 곱해도 절대로 3으로 나눈 것을 커버할 수 없다. 추가적으로 수열의 크기가 N이기 때문에, v[0]으로 나올 수 있는 후보를 하나씩 체크해서 가능한 경우를 모두 확인해주면 된다. 이때, 주어진 수에 v[i] / 3이나 v[i] * 2가 존재하는지를 쉽게 파악하기 위해서 set 자료구조를 활용하였다. 시간 복잡도는 $O(n^2logn)$이므로 시간 안에 충분히 통과한다. Code #include #define fastio cin.tie(0)->..

Approach 다익스트라를 2번 돌리는 것은 쉽게 파악할 수 있다. 이 문제에서 가장 중요한 지점은, 최단 경로를 전부 찾고 해당하는 최단 경로를 지우는 것이다. 이를 위해 기존의 parent를 1개만 저장해둔 것에서 vector를 통해 저장해두면, 최단 경우에 해당하는 모든 간선들을 찾고 지울 수 있다. 추가적으로, 포인터 등을 활용해서 간선을 조금 더 효율적으로 지울 수는 있다. (toysmars님의 제출 코드 참고) Code #include #define fastio cin.tie(0)->sync_with_stdio(0) using namespace std; typedef long long ll; typedef pair pii; int move_x[4] = {-1, 1, 0, 0}; int mov..