1. 문제 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 2. 풀이 크게 어려울 것이 없는 단순 구현문제다. 아래 풀이한 코드를 보면 충분히 흐름을 이해할 수 있을 것으로 생각된다. 다만, 해당 문제에서 가장 중요한 조건이 하나 있는데, 미세먼지 확산에 대한 것이다. 바로 미세먼지는 모든 칸에서 동시에 확산된다는 점인데, 이는 다시 말해 단순 반복문을 통해서 확산된 미세먼지가 동일한 쿼리 내에서 상호 영향을 주면 안된다는 얘기가 된다. 즉, 각 기준점의 확산량을 누적할 수 있는 별도의 배열을 선언해야 한다는..
1. 문제 14891번: 톱니바퀴 첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 www.acmicpc.net 2. 풀이 단순 구현 문제이지만 문제에서 유의해야 할 점은 바로 톱니바퀴가 연쇄적으로 상태가 바뀌는 것이 아니라는 점이다. 이게 무슨 말이냐면 아래 이미지에서 1번 톱니바퀴를 회전시킨 결과에 따라서 2, 3, 4번 톱니바퀴의 회전이 결정되는 것이 아니라는 말이다. 즉, 아래 이미지와 같이 정적인 상태에서 회전 여부가 결정이 되고 최종적으로 한 번에 회전하게 된다는 것이다. 회전에 대한 결과가 다음 회전에 대해 영향을 미치지 않게 구현하기 위해서는 ..
1. 문제 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 2. 풀이 구현/시뮬레이션 유형의 문제로, 우선 문제를 꼼꼼하게 이해하는 것이 무엇보다 중요한 문제다. 뱀의 움직임은 크게 아래와 같이 세 가지 유형으로 분리해서 생각할 수 있다. 1) 더 움직일 수 없는 경우 지도에서 벗어나려 하거나 움직이고자 하는 칸에 뱀의 몸뚱이가 있는 경우 게임은 종료된다. 2) 사과를 먹는 경우 사과를 먹는 경우 몸 길이가 1 늘어나게 된다. 문제에서는 복잡하게 설명하였으나, 다음칸으로 전진한 머리를 유지하고 꼬리는 삭제되지 않는다..
1. 문제 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x, y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지 www.acmicpc.net 2. 풀이 구현 문제이지만 주사위를 굴리는 방법을 구현하는 과정에서 실수를 범하기 좋은 유형의 문제다. 하지만 문제는 꽤나 단순하게 접근할 수 있는데, 그 이유는 주사위 6면에 대해서는 1차원 배열로 선언이 가능하며 네 방위(동, 서, 남, 북)로 움직이는 행위만 잘 정의해주면 되기 때문이다. 따라서, 각 배열의 index에 대해 위치를 사전에 정의해두고, 이를 네 방면으로 굴렸을 때 인..
1. 문제 14503번: 로봇 청소기 첫째 줄에 방의 크기 $N$과 $M$이 입력된다. $(3 \le N, M \le 50)$ 둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 $(r, c)$와 처음에 로봇 청소기가 바라보는 방향 $d$가 입력된다. $d$가 $0$인 경우 북쪽 www.acmicpc.net 2. 풀이 단순한 구현 문제이지만, 로봇의 동작이 다소 복잡하게 정의되어 있어 난이도가 올라간 것으로 보인다. 하지만 문제에서 정의한 청소기의 동작 방식을 순차적으로 잘 구현만 한다면, 큰 어려움은 없다. 현재 칸이 아직 청소되지 않은 경우, 현재 칸을 청소한다. 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 없는 경우, 바라보는 방향을 유지한 채로 한 칸 후진할 수 있다면 한 칸 후진하고 1번으로 돌..
1. 문제 16959번: 체스판 여행 1 크기가 N×N인 체스판이 있고, 체스판의 각 칸에는 1부터 N2까지의 정수가 한 번씩 적혀있다. 지학이는 이 체스판을 이용해서 재미있는 게임을 해보려고 한다. 지학이가 가지고 있는 말은 나이트, www.acmicpc.net 2. 풀이 BFS를 응용해볼 수 있는 좋은 유형의 문제로, 문제의 조건에 따라 말의 방문 처리를 어떻게 꼼꼼하게 할 것 인가가 문제의 키 포인트이다. 먼저 지학이가 수행할 수 있는 동작과 조건을 살펴보자. 1) 동작 말을 다른 유형의 말로 변경한다(나이트, 룩, 비숍) 말을 이동시킨다 2) 조건 같은 칸을 여러 번 방문해도 된다. 1부터 N² 까지 각 칸을 순차적으로 방문해야 한다. 번호에 따라 순차적으로 방문해야 하므로, 체스판을 입력 받음과..