문제 링크 www.acmicpc.net/problem/9328 9328번: 열쇠 상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 www.acmicpc.net 풀이 범위가 작아 무슨 짓을 해도 풀 수 있습니다. 1) 저는 bfs를 여러 번 돌려서 풀었는데, 매번 시작할 수 있는 시작점에서 출발해 갈 수 있는 데까지 가줍니다. 이 시작점은 현재 갖고 있는 열쇠 현황에 따라 달라지기 때문에 매번 새로 구해주어야 합니다. 2) 탐색 중 열쇠를 먹었다면 업데이트하고, 그 열쇠로 열 수 있는 문은 다음번 bfs에서 통과할 수 있게 됩니다. 이런 방식으로 더이상 서류나 열쇠를 먹..
문제 링크 www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 풀이 각 앱별로 사용 중인 메모리 $m$, 비활성화 했을 경우 비용 $c$가 주어집니다. 일반적으로 생각했을 땐 메모리의 모든 범위에 대해 최소 비용을 구하는 배낭 dp인데, 메모리의 범위가 너무 커 배열로 잡을 수 없습니다. 관점을 좀 달리하여 모든 비용에 대해 확보할 수 있는 최대의 메모리를 구해줍시다. 비용의 범위는 최대 100이므로 충분히 가능합니다. 그 후 비용 0부터 올라가며 우리가 필요한 메모리..
문제 링크 www.acmicpc.net/problem/7453 7453번: 합이 0인 네 정수 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다. www.acmicpc.net 풀이 $a+b+c+d = 0$인 조합의 개수를 찾아야합니다. 나이브하게 풀면 $O(N^4)$의 복잡도로 통과하지 못합니다. 1) 이를 $a+b = -(c+d)$로 생각하여 양 변을 따로 봅시다. 각각 $(a+b)$, $(c+d)$의 모든 조합을 구하는데 $O(N^2)$의 복잡도가 듭니다. 2) $a+b$ 배열의 각 원소마다, $c+d = -(a+b)$를 만족하는 $c+d$ 조합의 수..
문제 링크 www.acmicpc.net/problem/2887 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 풀이 점이 10만 개입니다. 이론상 모든 점을 연결할 수 있으므로 완전 그래프 꼴이긴 합니다. 간선이 너무 많은 것만 빼면 전형적인 최소 스패닝 트리 문제입니다. 근데 잘 생각해보면 굳이 모든 간선을 볼 필요가 없습니다. 우리는 최소 스패닝 트리를 만들거니까 축별로 정렬 후 이웃한 점끼리만 간선을 맺어주면 됩니다. 이게 왜 되는지 그림으로 살펴봅시다. 어떤 한 축만 고..
문제 링크 www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 풀이 방향성 있는 그래프가 주어집니다. 출연 순서를 정할 수 없는 상황은 그래프에 사이클이 있는 경우입니다. 위상 정렬을 돌리되, 방문할 수 없는 정점이 있다는 말은 그 정점의 indegree가 0이 되지 않는다는 말이고, 사이클이 있다는 말과 동일합니다. 위상 정렬 후 모든 정점을 방문할 수 있는지 확인하여 답을 출력해줍시다. 정답 코드 #include using namespac..
문제 링크 www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 풀이 1) 어떤 정점에서 시작하든 최소 비용은 같습니다. 그러니 0번부터 조집시다. A->B->...->F->A B->C->...->A->B 모두 같습니다. 2) 현재까지 어느 정점들을 탐색해왔는지 비트 마스킹으로 관리합니다. 그 집합과 현재 정점을 기준으로 dp를 전개합니다. 다음으로 이동할 정점을 고를 때 집합에 포함되지 않는 정점을 고르면 됩니다. 3) 기저..
문제 링크 www.acmicpc.net/problem/2342 2342번: Dance Dance Revolution 입력은 지시 사항으로 이루어진다. 각각의 지시 사항은 하나의 수열로 이루어진다. 각각의 수열은 1, 2, 3, 4의 숫자들로 이루어지고, 이 숫자들은 각각의 방향을 나타낸다. 그리고 0은 수열의 마 www.acmicpc.net 풀이 지시 사항의 인덱스, 왼발의 위치, 오른발의 위치를 가지고 dp를 돌려줍시다. 각각 왼발을 옮겼을 때, 오른발을 옮겼을 때로 전개하며, 현재 위치와 다음 위치의 차이에 따른 값만 바꿔주며 정답에 더해주면 됩니다. 정답 코드 #include #define INF 0x3f3f3f3f using namespace std; int d[111'111][5][5]; int..
문제 링크 www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1≤N≤32,000), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이 www.acmicpc.net 풀이 1) $i$번 학생 바로 앞에 서야하는 다른 학생이 있으면 $i$번 학생의 indegree를 증가시켜줍니다. 2) 순서가 확정된 학생들 외에는 자유롭게 세워도 되므로, indegree가 0인 모든 정점을 큐에 넣습니다. 3) 위상 정렬을 돌립니다. 정답 코드 #include using namespace std; using vi = vector; using vvi ..
문제 링크 www.acmicpc.net/problem/2239 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net 풀이 생각 없이 풀 수 있는 백트래킹 문제입니다. 각 행, 열, 3*3 그룹마다 체크 배열을 만들어 두고 1~9까지의 수가 들어 있는지 비트 마스킹으로 확인합니다. 칸 $(i, j)$는 $(i/3)*3 + j/3$ 번째 그룹$(0-based)$에 포함되어있다는 것만 생각해주시면 됩니다. 정답 코드 #include using namespace std; using pii = pair; using v..
문제 링크 www.acmicpc.net/problem/2166 2166번: 다각형의 면적 첫째 줄에 N이 주어진다. 다음 N개의 줄에는 다각형을 이루는 순서대로 N개의 점의 x, y좌표가 주어진다. 좌표값은 절댓값이 100,000을 넘지 않는 정수이다. www.acmicpc.net 풀이 어떤 삼각형의 세 좌표가 주어졌을 때, 그 삼각형의 넓이는 외적값의 절반입니다. CCW를 구하는데도 외적이 쓰이구요. CCW에 대해선 다음 글을 참고해주세요. CCW로 세 점의 방향성 판별하기 - 데구리 블로그 이걸 확장해서 다각형의 면접을 구할 때도 CCW를 사용할 수 있습니다. 한 점을 기준으로 잡고, 연속한 두 점마다 CCW의 값을 더해준 뒤, 합의 절댓값을 2로 나눠주면 됩니다. 놀랍게도 이 방법은 오목 다각형에도..