본문 바로가기

알고리즘66

[백준 15686] 치킨 배달 (C++) A. 문제설명 https://www.acmicpc.net/problem/15686 문제에 대한 자세한 설명은 링크 참조 1. N * N 배열 크기의 도시가 존재 2. 배열의 각 좌표에는 0: 빈칸, 1: 집, 2: 치킨집이 존재 3. 각 집에서 가장 가까운 치킨집의 거리를 '치킨거리'라고 하는데, 이는 |r1-r2| + |c1-c2|로 구한다. 4. 여기서, 주어진 치킨집 중 M개의 치킨집만을 남기고 폐업하려고 하는데, 그 조건은 남은 M개의 치킨집이 도시의 모든 집들의 치킨거리가 최소가 되는 경우이다. 5. M개의 치킨집을 살렸을 때 도시의 최소치킨거리를 구할 것 B. 접근법 먼저 이 문제에서 내가 생각한 방식은 DFS이다. M개의 치킨집을 살리는 것에 대한 조합을 DFS로 모두 구해야하고, 그 조합을.. 2020. 3. 28.
[백준 15685] 드래곤 커브 (C++) A. 문제설명 https://www.acmicpc.net/problem/15685 문제에 대한 자세한 설명은 링크 참조 1. 시작점, 방향, 진행세대 수로 정의되는 드래곤 커브가 존재 2. 각 드래곤 커브는 시작점에서 시작해서 출발방향으로 이동하고, 세대의 진행에 따라 이전 세대의 드래곤 커브를 90도 회전시킨 후 끝점에 이어붙여서 확장 3. 주어진 세대로의 확장이 완료된 후 전체 좌표평면 내 드래곤커브가 걸쳐져 있는 사각형의 갯수 계수 이제 이걸 어떻게 그려야하나... 그림을 그려서 풀어야 할까? B. 접근법 처음 이 문제를 받아보고 생각이 든 것은 드래곤 커브 자체의 그림에 대한 생각이었다. 그러나, 이 문제에서 집중해야 할 것은 그림 자체가 아니라 규칙성이다. 각 세대별로 이전 세대의 특징을 가지고.. 2020. 3. 28.
[백준 5373] 큐빙 (C++) A. 문제설명 https://www.acmicpc.net/problem/5373 문제에 대한 자세한 설명은 링크 참조 1. 3 * 3 정육면체의 큐브가 존재 2. 큐브의 각 면에는 위:흰색, 아래:노란색, 앞:빨간색, 뒤:오렌지색, 왼:초록색, 오른:파란색으로 색칠됨 3. 큐브를 돌리는 횟수와 돌리는 면 및 방향(시계/반시계)이 주어짐 4. 주어진 대로 큐브를 모두 돌리고 난 후 윗면 9개 칸의 색상을 출력 문제의 조건은 사실 간단하다. 3 * 3 정육면체 루빅스 큐브를 구현하여 모사하면 되는 것 B. 접근법 큐브를 6개의 3*3 배열로 나누어 좌표에 유의하여 구현한다. 면의 회전방향이 보는 각도에 따라 달라지며 우리가 정의하는 X, Y의 좌표가 뒤집어진 면에서는 그에 맞추어야 하므로 전개도를 그려 헷갈.. 2020. 3. 12.
[백준 17144] 미세먼지 안녕! (C++) A. 문제설명 https://www.acmicpc.net/problem/17837 자세한 설명은 링크참조 1. R * C 칸의 방에 미세먼지 양 정보가 주어짐 2. 동시에 공기청정기 위치 (r, c)도 주어짐. 공기청정기는 세로 2칸 크기 3. 매 초마다 미세먼지 확산과 공기청정기 작동이 일어남 4. 미세먼지가 인접한 네 방향으로 확산 4-1. 공기청정기가 있거나, 벽이면 그 방향으로는 확산 X 4-2. 확산되는 양은 먼지량/5이고 소수점은 버린다. 4-3. 기존 칸에 남은 미세먼지의 양은 '먼지량 - (먼지량/5) * (확산된 방향의 개수)' 5. 공기청정기 작동 5-1. 위쪽은 반시계, 아래쪽은 시계방향으로 벽을 타고 공기이동 5-2. 먼지는 바람의 방향대로 한 칸씩 이동. 바람은 먼지없는 바람이고,.. 2020. 3. 5.
[백준 17140] 이차원 배열과 연산 (C++) A. 문제설명 https://www.acmicpc.net/problem/17140 자세한 설명은 위 링크에서 1. 3 * 3 배열이 존재 2. 배열에 매 초마다 연산을 적용 2-1. R 연산: 배열 A의 모든 행에 대해서 정렬을 수행한다. 행의 개수 ≥ 열의 개수인 경우에 적용 2-2. C 연산: 배열 A의 모든 열에 대해서 정렬을 수행한다. 행의 개수 < 열의 개수인 경우에 적용 3. 여기서 정렬의 의미는 각 행 또는 열 내 숫자들을 계수, 숫자들이 발생한 횟수를 조건에 맞추어 정렬한다는 것 * [1, 1, 2, 3, 3] 의 배열이 존재한다고 가정. 1이 2개, 2가 1개, 3이 2개이므로 [1, 2, 2, 1, 3, 2]의 새로운 배열을 만듦 4. 새로 만든 배열은 아래와 같이 정렬됨 4-1. 등장.. 2020. 3. 5.
[백준 17837] 새로운 게임 2 (C++) A. 문제설명 https://www.acmicpc.net/problem/17837 문제의 자세한 설명은 위 링크에 자세하게 나와있으니 각설하고, 핵심을 요약하자면 1. N * N 체스판이 존재 2. 각 체스판의 엔트리에는 흰색 / 빨간색 / 파란색으로 표시 3. 체스판 위에 말들을 올림(숫자) 4. 각 말들은 이동방향이 정해져있고, 각 턴마다 해당 방향으로 한칸씩 이동 5. 각 말들은 이미 다른 말이 점유하고 있는 칸으로도 이동할 수 있는데, 5-1. 말 A가 말 B가 있는 위치로 이동하면 위에 올라탈 수 있음. 즉 A | B 에서 | A/B 로 올라타게 됨 5-2. 이미 말 여러개가 겹쳐져 있는 칸에서 말이 이동시, 위에 태우고 있는 말들을 같이 이동시킴. 즉 A/B | C 에서 B가 C쪽으로 이동하면.. 2020. 3. 5.

티스토리툴바