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

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

Approach 트리의 지름과 동일한 문제이다. 맨 마지막에 "The labyrinth is designed in such a way that there is exactly one path between any two free blocks"라고 했으므로 사이클이 없는 그래프이므로 트리 구조를 띄고 있음을 쉽게 파악할 수 있다. Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; typedef pair ii; int move_x[4] = {-1, 1, 0, 0}; int move_y[4] = {0, 0, -1, 1}; bool r[1000][1000]; bool visite..

Approach 조금은 발상적일 수 있는데, 간선을 2번 방문하지 않는 경우는 가장 오른쪽 노드들을 방문할 때가 유일하다. 따라서 트리의 간선의 수는 component에 속한 정점의 수 - 1이라는 것을 생각해보면 해당 값의 2배에서 맨 오른쪽 노드들을 방문하는 간선들의 개수만큼을 제거해주면 된다. Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; bool visited[100001]; class tree{ public: int l; int r; tree() : l(-1), r(-1) {} tree(int a, int b) : l(a), r(b) {} }; vector ..