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..

Approach 잘 생각해보면, 도착 높이에 대한 가치는 이미 고정되어 있는 상황이므로 해당 장소까지 방문하는데 소모된 체력을 최소한으로 만들기 위한 경로를 찾는 문제로 바뀐다. 추가적으로 소모된 체력은 이동 거리와 비례하는 상황이므로, 문제 상황은 최단 거리를 구하는 문제로 바뀌게 된다. 따라서 해당 지점에서 다익스트라 문제임을 쉽게 파악할 수 있다. 문제 조건에서 고려해야할 점은 다음과 같다. 1. 목표지점 도착 전까지는 높이가 올라가는 방향일떄만 dist 갱신이 가능하다. 2. 출발점과 목표지점, 목표지점과 고려대학교까지 도달하는 경로가 존재하지 않을 수 있다. 만약 한 경우라도 없다면 계산에서 제외시켜주어야 한다. 이를 위하여 다익스트라 기준점을 출발점과 고려대학교로 잡으면 된다. (고려대학교로 ..

Approach 다익스트라에 parent 배열을 활용해주면 쉽게 풀 수 있다. 다익스트라를 돌면서 갱신될 때마다 parent[to] = cur를 수행해주고, 역으로 출발점이 될 때 까지 계속해서 역으로 타고가면 경로를 추적할 수 있다. 약간 DP 역추적 같은 느낌으로 이해하면 충분하다. 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 INF = 20000; int main() { fastio; int n, m; cin >>..

Approach 최단 시간을 찾는 상황이므로 다익스트라 유형임을 쉽게 파악할 수 있다. 점이 100개밖에 안되므로, 배열을 통해 충분히 관리할 수 있다. 추가적으로 모든 지점을 향해서 발사할 수 있으므로, 다익스트라에서 모든 정점에 대해서 확인해주면 된다. 다만, 처음 위치하는 곳에서는 무조건 걸어야하므로 따로 boolean flag를 통해 정리해주면 된다. Code #include #define fastio cin.tie(0)->sync_with_stdio(0) using namespace std; typedef long long ll; typedef pair pii; typedef pair pdd; typedef pair pdi; int move_x[4] = {-1, 1, 0, 0}; int move..