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

Approach 최소 몇 개 선택하는지를 묻는 것에서 BFS 냄새가 났으면 충분하다. 다만, 기존에 처리한 숫자들은 다시 중복해서 처리할 이유가 없으므로 일종의 visited를 처리해야하는데 숫자들의 숫자는 8!밖에 안되는데 해당 숫자들을 전부 다 담기 위해서는 훨씬 더 큰 배열의 크기가 필요하게 된다. 따라서 set 자료구조를 활용해서 처리해주면 된다. + 숫자가 1~8까지 존재하므로 해당 숫자 - 1을 처리함으로써 총 3개의 비트로 해당 원소를 방문하였는지를 처리할 수 있다. 숫자가 8개이므로 총 24개의 비트를 가지고 visited를 처리할 수 있는 것이다. 위의 접근 방법 같은 경우는 string 자료구조를 써야하는 반면, 이 방식은 int 자료형으로도 처리할 수 있기 때문에 메모리 측면에서는 우..

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

Approach 문제에서 주어진 트리 그림을 잘 보면, 너비 번호가 중위순회를 통해 방문하는 순서와 완벽하게 동일함을 쉽게 파악할 수 있다. 추가적으로 같은 높이 기준으로 넓이가 가장 최대인 것을 찾고 싶은 상황이므로 dfs를 하는 정점의 높이가 어떻게 되는지를 트래킹 해야한다. 따라서 dfs의 parameter에 높이 정보를 추가로 주입해주면 된다. Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; class tree{ public: int left; int right; tree() : left(-1), right(-1) {} tree(int x, int y) : le..

Approach 사실 예제 입력 2에 대한 설명을 보고 가장 큰 아이디어를 얻었다. 문제에서 1번으로 가는 길은 유일하다는 표현을 통해 사이클이 없는 트리 구조임을 쉽게 파악할 수 있다. 따라서 점들의 관계를 표시해보면, 일종의 1번 노드를 루트 노트로 하는 트리로 이해할 수 있다. 그런데, 자식 노드를 기준으로 점차적으로 위로 올라오면서 양이 들어오는 양상이다. 추가적으로 해당 점이 양이 있는 곳이라면 자식에서 올라오는 양의 수에 해당 점에 있는 양의 수를 더해주면 되고, 반대로 늑대가 있는 점이라면 자식에서 올라오는 양의 수에 해당 점에 있는 늑대의 수를 뺴주면 된다. (만약 음수가 나올 경우에는 0으로 만들어주면 된다.) 늑대는 이동하지 않는 상황이므로 dfs를 돌면서 양의 값을 ret으로 잡으면 ..