https://www.acmicpc.net/problem/17144 미세먼지가 확산되고 공기청정기가 작동하는 방법을 어렵지 않게 이해할 수 있었다. 해결 순서는 다음과 같다. 1. 미세먼지를 확산시킨다. 2. 공기청정기를 작동한다. 3. 위 과정을 t번 반복한다. 중요한 것은 초기에 미세먼지가 입력되는 위치와 값을 어떤 자료구조에 저장하고 있어야 한다. 만약 현재 위치에 미세먼지가 없었고, 옆방향에서 확산된 미세먼지로 인해 현재 위치에 미세먼지가 생길 수 있는데 이러한 경우는 현재 위치에서 미세먼지 양을 조절하지 않는다. 따라서 입력된 미세먼지의 좌표값과 미세먼지의 양을 큐에 따로 저장한 뒤 큐에서 하나씩 빼가면서 확산시켰다. 확산되는 방향은 상하좌우 4방향이므로 각 위치에서 4번씩만 확인하면 된다. 여..

https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미한다. r과 c는 1부터 시작한다. 이 도시에 사는 사람들은 치킨을 매우 좋아한다. 따라서, 사람들은 "치킨 거리"라는 말을 주로 사용한다. 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다. 즉, 치킨 거리는 www.acmicpc.net 문제를 읽었을 때 전반적으로 어렵거나 이해가지 않는 내용은 딱히 없었다. 전체 치킨집에서 M개만큼 선택할 수 있는 모든 경우의 수를 ..

https://www.acmicpc.net/problem/15685 15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커브의 시작 점, d는 시작 방향, g는 세대이다. (0 ≤ x, y ≤ 100, 0 ≤ d ≤ 3, 0 ≤ g ≤ 10) 입력으로 주어지는 드래곤 커브는 격자 밖으로 벗어나지 않는다. 드래곤 커브는 서로 겹칠 수 있다. 방향은 0, 1, 2, www.acmicpc.net 처음 문제를 이해할 때 드래곤 커브가 다음 세대로 가는 경우 끝 점을 기준으로 시계 방향으로 90도 회전시킨다는 말을 반대로 이해해..

https://www.acmicpc.net/problem/14891 14891번: 톱니바퀴 첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 시계방향 순서대로 주어진다. N극은 0, S극은 1로 나타나있다. 다섯째 줄에는 회전 횟수 K(1 ≤ K ≤ 100)가 주어진다. 다음 K개 줄에는 회전시킨 방법이 순서대로 주어진다. 각 방법은 두 개의 정수로 이루어져 있고, 첫 번째 정수는 회전시킨 톱니바퀴 www.acmicpc.net 문제에서 제시한 조건을 정리하면 아래와 같다. - 현재 톱니바퀴가 회전하지 않는다 -> 옆에 있는 톱니바퀴도 회전하지 않는다. (이 ..

https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net Greedy 알고리즘은 가장 큰 것, 작은 것 등 원하는 방향을 기준으로 규칙을 지키면서 접근하면 된다. 정렬 알고리즘을 함께 사용하는 경우가 많다. 돈을 인출하는데 필요한 시간의 합이 최소값이 되도록 해야 하므로 돈을 인출하는데 가장 많은 시간이 걸리는 사람은 마지막에 인출해야 한다. 마찬가지로 돈을 인출하는데 가장 적은 시간이 걸리는 사람이 가장 먼저 돈을 인출하는 것이 좋다. 따라서 우선 오름차순으로 정렬한 뒤 접근하는 ..