Approach 대표적인 다익스트라 문제이다. w가 양수인 최단 경로를 구하는 상황이므로 다익스트라로 구할 수 있다. Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; typedef pair pii; const int INF = 987654321; int v, e; vector dist; vector edge; bool visited[20000]; int main(void) { fastio; memset(visited, 0, sizeof(visited)); cin >> v >> e; edge = vector(v); dist = vector(v); fill(dist.beg..

Approach 그래프 탐색 관련한 문제라는 것은 문제를 읽자마자 쉽게 파악할 수 있다. 문제 상황에서 가장 크리티컬한 지점은 탐색과정에서 보석을 얼마나 가지고 있는지를 기억해야한다는 것이다. 왜냐하면, 보석을 얼마나 가지고 있는지에 따라서 방문할 수 있는 지역이 달라지기 때문이다. 따라서 BFS를 돌리는 과정에서, 보석을 얼마나 가지고 있는지를 기억하고 있으면 된다. 같은 지역에 있는 보석은 1번만 주울 수 있으므로, 비트마스킹을 통해 1개의 정수로 어느 지역의 보석을 가지고 있는지를 쉽게 저장해놓을 수 있다. 추가적으로 같은 지역을 방문하더라도 보석이 달라지면 경향성이 달라지므로, visited를 2차원 배열로 잡는다. 위 문제와 비슷한 느낌으로 이해해주면 된다. https://viyoung.tist..

Approach 문제에서 이동 횟수의 최솟값을 묻는 상황이므로, BFS를 바로 떠올려주면 된다. 다만, 이 문제에서 되게 독특한 지점은 각 이동하는 상황에서 키를 가지고 있는지 여부가 굉장히 중요하다. 따라서 키를 가지고 있는지 여부를 set으로 넘겨줘도 되지만, 비트마스킹을 활용해주면 숫자 하나로 모든 것을 판단할 수 있게 된다. 추가적으로 visited도 신경써야 하는데, 키가 달라진다면 기존에 방문했던 곳이라도 양상이 달라질 수 있기 때문에 visited를 3차원으로 잡아주면 된다. 다음 문제와 비슷하게 느낌을 받았으면 충분하다. (위 문제도 단순히 같은 위치를 방문한다고 해서 같은 의미는 아니므로 차원을 1개 늘렸다.) https://viyoung.tistory.com/334 [백준 2206번] ..

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 일단 처음 접근한 방법은 세그먼트 트리 + 이분 탐색이다. 잘 생각해보면 bitwise or 계산 결과는 단조증가할 수 밖에 없다. 구간의 시작점을 1 ~ N까지 이동시키면서, lower_bound를 해서 k가 나오면 해당 구간을 출력해주면 된다. 구간 별 xor 결과는 세그먼트 트리를 통해서 관리를 하고, 이를 이분탐색으로 만족하는 구간이 있는지를 파악해주면 된다. 대회가 끝나고 공식 해설을 보고, 다음과 같은 방법으로 풀면 좀 더 쉽게 처리할 수 있음을 파악하였다. 잘 생각해보면, k와 xor한 결과가 k이면 구간 안에 들어갈 수 있는 수이고, 그렇지 않으면 무조건 들어갈 수 없는 수이다. 따라서, 들어갈 수 있는 숫자들을 전부 다 더했을 때 k가 나오면 문제조건을 만족할 수 있는 구..

Approach 전형적인 비트마스킹 문제이다. Add : t의 i번째 비트를 키고 싶은 경우 ( t |= (1 v; if(v == "add"){ int t; cin >> t; bitmask |= 1 > t; bitmask &= ~(1 > t; if(bitmask & (1