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

Approach 자료구조 수업에서나 나올법한 문제이다. 잘 생각해보면 preorder가 하는 역할을 잘 생각해보면, 루트 노트부터 시작해서 왼쪽 방향무터 서브트리의 루트노드를 지속적으로 방문하게 된다. 따라서 해당 순서를 inorder에서 바라보게 되면, 발견한 index를 기준으로 왼쪽은 자신을 기준으로 왼쪽과 오른쪽으로 subtree를 나누어서 생각할 수 있다. 세그트리 짜는 것처럼, start, end index를 함수의 입력값으로 두고 계속해서 좁혀가면 쉽게 구할 수 있다. Code #include #define fastio ios_base::sync_with_stdio(0). cin.tie(0), cout.tie(0) using namespace std; vector preorder; vecto..