Approach 문제를 잘 관찰해보면, 현재 방문했던 주유소 중 주유 비용이 가장 싼 것이 무엇인지를 저장해두는 것이 중요하다는 것을 쉽게 파악할 수 있다. 추가적으로, 현재까지의 주유 비용이 가장 싼 것이 어느 것인지에 따라서 특정 점까지 방문하는데 필요한 비용이 다르므로 DP처럼 차원을 1개 더 잡아줘서 다익스트라를 돌려주면 된다. https://viyoung.tistory.com/380 [백준 10217번] [Dijkstra / DP] KCM Travel Approach 잘 생각해보면, 비용 단위로 최단거리를 구해주면 된다. https://viyoung.tistory.com/369 문제와 유사하다. Code #include #define fastio cin.tie(0)->sync_with_stdio..

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 아마 다익스트라 문제임은 쉽게 파악할 수 있을 것이다. 이 문제를 풀기위해 가장 중요한 점은, 각 경로 별로 통행료와 간선의 개수를 파악하는 것이다. 왜냐하면, 통행료가 올라감에 따라 간선의 개수가 많을수록 통행료가 증가하기 때문이다. 즉, 간선의 개수 별로 최소 통행료를 구하는 것이 필요하고 이를 DP느낌으로 처리해주면 된다. dist[i][j] : 출발점에서 정점 i까지 j만큼의 간선을 통과했을 때의 최소 통행료 Code #include #define fastio cin.tie(0)->sync_with_stdio(0) using namespace std; typedef pair pii; typedef unsigned long long ull; typedef tuple tiii; typ..

Approach 문제에서 주어진 힌트를 보고 잘 생각해보면, 채우는 방법은 한번에 2칸, 한번에 4칸, 6칸, .. 2k칸이 존재한다. 그리고 2칸을 채우는 방법만 3가지이고, 나머지의 경우는 2가지 존재한다. 또한 한번에 2칸 채우는 것을 2번 반복한 것과, 한번에 4칸 채우는 것을 1번 반복한 것의 이후 과정은 완벽학게 동일하므로 이를 중복하여 계산하지 말고 DP로 저장해두면 계산 시간을 줄일 수 있다. (물론 n이 되게 작아서 시간 안에는 무조건 들어온다.) dp[i] : i번째 칸까지 채웠을 때 3 x N크기의 벽을 채우는 경우의 수 dp[i] = dp[i + 2] * 3 + dp[j] * 2 for all j s.t j % 2 == 0 & j 2 Code #include #define fasti..

Approach 완전탐색으로 구현하기에는 100자리수이므로 시간이 너무 부족하다. (물론 숫자를 단순히 돌리기에는 long long으로도 부족하다.) 잘 생각해보면, 계단수를 체크하기 위해 필요한 계산은 총 O($2^N$)이지만, 중복되는 연산이 너무 만다는 것을 알 수 있다. 이를 줄이기 위해서 memoization을 활용한 DP를 사용해주면 된다. dp[i][j][visited] : number of length is i, current number is j, list of using number is visited (Using bitmask) Therefore dp[i][j][visited] = dp[i + 1][j - 1][visited | (1

Approach DFS나 BFS를 통해 완전탐색을 하게 되면 시간 초과가 난다. 잘 생각해보면, 현재 켜져있는 발전기의 양상이 동일하면 뒤에 벌어지는 상황도 동일한데, 여러번 계산을 하기 때문에 불필요하게 시간을 많이 소모하게 된다. 이 지점에서 DP를 활용하여 켜져있는 발전기의 양상의 상황을 memoization하면 시간 초과를 막을 수 있다는 것을 파악할 수 있다. 가장 쉽게 생각할 수 있는 방법은 dp table에 해당 발전기의 양상을 만들기 위해서 필요한 최소 비용을 저장해두는 것이다. 하지만, 특정 상태에서 발전기를 켜는데 최소의 비용이 들었다고 해도, 이후의 발전기가 켜지는 양상에 따라서 더 최소의 비용이 존재할 수 있기 때문에 독립적으로 계산할 수 없기에 계속해서 업데이트를 해주어야 한다. ..

Approach 완전 탐색하기에는 16!의 가능성을 모두 탐색해야하므로 TLE가 날 수 밖에 없다. 사실 잘 생각해보면, 중복되는 연산이 상당히 많다는 것을 알 수 있다. 예를 들어 1 3 2 4 순서로 방문을 하든, 1 2 3 4 순서로 방문하든 뒤의 방문하는 순서가 동일하다고 하면 뒤에 비용은 완전히 동일하다. 따라서 DP를 활용하면 시간 복잡도를 줄일 수 있다. 어느 마을을 현재 망문했는지 정보가 필요하므로 DP 식에 방문 정보가 필요하게 된다. DP[i][visited] : visited만큼의 마을을 방문하고 현재 i번쨰 마을에 위치해 있다고 했을 때 , TSP 최소비용 이 과정에서 visited를 vector로 관리해도 되지만, 비트마스킹을 활용해서 쉽게 어느 마을을 방문했는지 알 수 있다. C..

Approach 완전 탐색으로 이 문제를 처리한다고 하면 비둘기집의 원리에 따라서 중복되는 연산이 매우 많다는 사실을 쉽게 캐치할 수 있다. dp[i] = i번째 수부터 시작하는 LIS 중 합이 가장 큰 값 dp[i] = max(v[i], max{dp[i + j] + v[i]}) for all j s.t v[i] < v[j] Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; vector v; int n; int dp[1001]; int memoi(int k){ int& ret = dp[k]; if(ret != -1) return ret; int cmp = v[k]; fo..