출항사

간단한 그래프 탐색 문제이다. 문제를 해석해보면, 직관적으로 펭귄과 가장 가까운 빨간 블록 2개를 찾고, 이 2개의 블록을 찾기까지 만나는 깰 수 있는 블록들의 개수를 세면 된다. 이게 가능한 이유는 그래프가 트리로 주어지고, 빨간 블록들이 서로를 찾으려면 무조건 펭귄을 지나야 하기 때문이다. 따라서 BFS나 DFS를 돌려 각 칸에 도달하기 까지 거리를 구하고, 1 > N >> S >> P; for (int i=1; i> x >> y; adj[x].push_back(y); adj[y].push_back(x); } visited[P] = 0; dfs(P); priority_queue pq; for (int i=1; i

일단 다익스트라 응용 문제인 것은 간단하게? 눈치챌 수 있다. 문제를 해석해보면, 아줌마는 총 10개의 노드를 순차적으로 이동한다고 한다. 여기서 문제의 핵심은 무조건 이 순서대로 이동한다는 것이다. 문제에서 주어지는 '나'의 순서는 필요없다. 그냥 모든 노드를 이동할 수 있고, 야쿠르트 아줌마를 만날 수 있는 노드가 몇번인지?를 구해야 한다. 아줌마가 이동할 노드들이 주어진다. 이때 각 노드별로 다익스트라를 돌려보자. 어차피 10번만 돌리면 되기 때문에, 10번의 다익스트라로 아줌마가 이동할 경로의 모든 최솟값 경로를 구할 수 있게 된다. 이제 나를 기준으로 다익스트라를 돌려주자. 내가 모든 노드에 도달할 수 있는 최소 비용을 구했다면, 이제 아줌마의 경로를 따라가봐야 한다. 아줌마가 i, i+1, i..

우선순위 큐 두개로 해결할 수 있는 문제이다. recommend 명령어가 1인지, -1인지에 따라 큰 값부터, 작은 값부터 찾아야 하는 값이 달라진다. 그래서 최대 힙과 최소 힙을 함께 사용하면 된다는 것을 눈치챌 수 있다. 그리고 별도의 방문 배열을 만들어서 각 문제가 solved 된 적이 있는지 확인하기로 하자. 그러면 최대힙에 있는 문제가 해결되었을때, 최소힙에서 이를 판별할 수 있게 된다. 구현이 조금 귀찮았던 문제다. #include #define MINF 0x7f7f7f7f #define INF 2000000000 #define MOD 10007 #define NUM 200010 #define X first #define Y second using namespace std; typedef lo..

스택으로 해결할 수 있는 문제이다. 현재 건물의 높이를 기준으로, 왼 오른쪽을 전부 바라봤을때 볼 수 있는 건물의 개수를 세라고 한다. 앞에서 부터 값을 저장한 스택과 뒤에서 부터 값을 저장한 스택을 사용하면 각 칸별로 바라볼 수 있는 건물의 개수를 구할 수 있다. 그다음 구해야 하는 것은 가장 가까운 건물의 번호이다. 가까운 건물의 번호는 스택으로 볼 수 있는 건물을 셀때 약간의 조건문을 통해 갱신하면 된다는 것을 쉽게 알아챌 수 있다. 스택을 갱신할 때마다 건물과 거리를 갱신하자. 그리고 이 번호가 갱신되는 순간 건물의 번호를 갱신해주면 된다. #include #define MINF 0x7f7f7f7f #define INF 2000000000 #define MOD 10007 #define NUM 10..

투포인터로 해결한 문제이다. N개의 물건 가격이 주어진다. 이때 1, 2, 3개 중 하나를 선택해 총 무게를 K로 만들 수 있는지 묻고 있다. N의 제한이 5000이하이기 때문에 2개를 선택하는 경우까지는 확인할 수 있지만, 3개를 선택하는 것이 관건이다. 정확히 K를 맞춰야 하는 것에 집중해보자. 그리고 하나의 물건을 기준으로 잡자. 이 무게를 X라고 할때 우리는 2개의 물건을 더했을때 N-K가 나오는 조합이 있는지 확인해야 하고 2개의 합이 N-K인지 확인하기 위해 투 포인터를 사용한다면, O(N)에 N-K 값이 있는지 알 수 있다. 따라서 O(N^2)에 3개를 선택한 경우도 구할 수 있다. #include #define MINF 0x7f7f7f7f #define INF 2000000000 #defi..

간단한 그래프 문제이다. 1번 노드를 기준으로 리프 노드까지 탐색하고, 이때 지나갈 수 없는 노드의 번호가 주어진다. 이때 리프 노드까지 정상적으로 탐색할 수 있는가?를 묻고 있다. 1번 노드를 기준으로 BFS or DFS를 돌리고, 리프 노드들을 확인해 하나라도 도달한 케이스가 있는지 확인하면 모든 조건을 만족할 수 있다. 현재 그래프가 유향 그래프로 주어지므로, 리프 노드는 간선의 개수가 0인 노드들이 될 것이다. 이 노드들을 모두 확인했을 때 도달한 적이 있다면 yes를, 하나라도 도달할 수 없다면 Yes를 출력하자. #include #define MINF 0x7f7f7f7f #define INF 2000000000 #define MOD 10007 #define NUM 100010 #define X..

팀의 초기 순위가 주어진다. 여기서 M개의 팀 쌍의 순위가 바뀌었다는 정보가 주어졌을 때, 가능한 경우인지 가능하다면 최종 순위는 몇 위인지 찾아야 한다. 그리고 가능하더라도 순위의 경우의 수가 1이 아니면?를 출력해야 한다. 순서가 정해져 있고, 이 순서를 기반으로 탐색을 진행해야 하기에 위상정렬을 떠올려볼 수 있다. 각 인덱스를 기준으로 자신보다 높은 순위가 몇개 남았는지를 세주자. M개의 정보가 들어온다. 이때 x, y중 초기 순위가 더 높은 값이 있고 작은 값이 있다. 이 둘을 바꾼다는 것은 이 우위가 바뀐다는 것이고, 간선의 방향을 뒤집어 줘야 한다. 그리고 나보다 높은 순위가 몇 개 남았는지 세는 값도 업데이트를 해줘야 한다. 자 이제 새롭게 만든 그래프를 기반으로 위상정렬을 돌리자. 이때 최..

간단한 탑다운 DP 문제이다. Ai = A[i/P] + A[i/Q]일때, An을 구해야 한다. N이 최대 1e12까지 가능하다. P와 Q는 최소 2부터 시작이다. 따라서 트리 구조로 탐색을 진행한다고 생각해봤을때, 트리의 깊이가 급격히 낮아지는 것을 알 수 있다. 중복되지 않는다고 해도 최대 log2 1e12안에 모든 탐색을 할 수 있다. 이는 깊이 38짜리 트리이다. 방문을 표시하기 위한 배열을 만들 수 없으니, map을 활용하기로 하자. 이제 배열대신 map에 값을 사용해서 재귀 탐색을 수행할 수 있다.이미 구했던 값을 다시 계산할 필요가 없으므로 메모이제이션 기법을 함께 활용하면 아주 간단히 풀린다. #include #define MINF 0x7f7f7f7f #define INF 2000000000..