개발 일지

문제 23291번: 어항 정리 (acmicpc.net) 23291번: 어항 정리 마법사 상어는 그동안 배운 마법을 이용해 어항을 정리하려고 한다. 어항은 정육면체 모양이고, 한 변의 길이는 모두 1이다. 상어가 가지고 있는 어항은 N개이고, 가장 처음에 어항은 일렬로 바 www.acmicpc.net 풀이 요구사항이 꽤 많은데, 차근차근 정리하며 구현하는것이 중요하다. 어항에 물고기 넣기 가장 물고기 숫자가 적은 어항에 물고기를 한마리 씩 넣어야 하므로, 어항 일차원 리스트를 정렬한 뒤 upper bound로 물고기를 넣어줘야하는 어항 인덱스를 찾았다. 공중부양 쌓기 1 맨 왼쪽 어항을 그 옆에있는 어항위에 쌓은 뒤, 조건에 따라 어항을 쌓아간다. 왼쪽에 몰려있는 두개 이상 쌓여있는 어항들을 빼서 90도 ..

문제 23290번: 마법사 상어와 복제 (acmicpc.net) 23290번: 마법사 상어와 복제 첫째 줄에 물고기의 수 M, 상어가 마법을 연습한 횟수 S가 주어진다. 둘째 줄부터 M개의 줄에는 물고기의 정보 fx, fy, d가 주어진다. (fx, fy)는 물고기의 위치를 의미하고, d는 방향을 의미한다. 방향 www.acmicpc.net 풀이 물고기의 이동 제한 조건은 상어의 존재, 보드 경계 그리고 냄새이다. 냄새는 생성되는 턴에 한번, 그리고 그로부터 두턴 더 남아있기 때문에 총 세번의 반복문을 돌고나면 0이된다는 점에 주의하자. 상어는 최적의 이동경로를 먼저 탐색한 뒤 그 경로를 따라 이동한다. 경로 탐색은 이동경로에 있는 물고기 숫자의 합과 이동경로 자체에 의해 결정되는데, 이는 heapq를 ..

문제 21611번: 마법사 상어와 블리자드 (acmicpc.net) 21611번: 마법사 상어와 블리자드 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그, 비바라기 마법을 할 수 있다. 오늘 새로 배운 마법은 블리자드이고, 크기가 N×N인 격자에서 연습하려고 한다. N은 항상 홀수이고, ( www.acmicpc.net 풀이 풀이에 상당한 시간이 소요된 문제이다. 본 문제에서의 핵심은, 블리자드 마법을 시전할 때외에는 전부 블리자드의 진행방향으로만 보드를 탐색한다는 것이다. 즉 마법 시전 이후엔 매번 보드를 블리자드 진행방향으로 탐색하기 보다는 일차원 리스트로 해석해서 구현하는것이 훨씬 편하다는 점을 눈치채야한다. 블리자드 진행방향에 있는 요소들을 일차원 리스트에 담을때는, 이전 문제들과 마찬가..

문제 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기를 크기가 N×N인 격자에서 연습하려고 한다. 격자의 각 칸에는 바구니가 하나 있고, 바구니는 칸 전체를 차지한다. 바구니에 저장할 수 있는 물의 양에는 제한이 없다. (r, c)는 격자의 r행 c열에 있는 바구니를 의미하고, A[r][c]는 (r, c)에 있는 바구니에 저장되어 있는 물의 양을 의미한다. 격자의 가장 왼쪽 윗 칸은 (1, 1)이고, 가장 오른쪽 아랫 칸은 (N, N)이다. 마법사 상어는 연습을 위해 1번 행과 N번 행을 연결했고, 1번 열과 N번 열도 연결했다. 즉, N번 행의 아래에는 1번 행이, ..

문제 유난히 추운 날씨가 예상되는 이번 겨울을 대비하기 위해 구사과는 온풍기를 설치하려고 한다. 온풍기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사과는 뛰어난 코딩 실력을 이용해 각 칸 (r, c)의 온도를 실시간으로 모니터링하는 시스템을 개발했다. (r, c)는 r행 c열을 의미한다. 구사과의 성능 테스트는 다음과 같은 작업이 순차적으로 이루어지며, 가장 처음에 모든 칸의 온도는 0이다. 문제의 그림에서 빈 칸은 온도가 0인 칸을 의미한다. 집에 있는 모든 온풍기에서 바람이 한 번 나옴 온도가 조절됨 온도가 1 이상인 가장 바깥쪽 칸의 온도가 1씩 감소 초콜릿을 하나 먹는다. 조사하는 모든 칸의 온도가 K 이상이 되었는지 검사. 모든 ..

문제 마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 얼음의 양을 의미한다. A[r][c]가 0인 경우 얼음이 없는 것이다. 파이어스톰을 시전하려면 시전할 때마다 단계 L을 결정해야 한다. 파이어스톰은 먼저 격자를 2L × 2L 크기의 부분 격자로 나눈다. 그 후, 모든 부분 격자를 시계 방향으로 90도 회전시킨다. 이후 얼음이 있는 칸 3개 또는 그 이상과 인접해있지 않은 칸은 얼음의 양이 1 줄어든다. (r, c)와 인접한 칸은 (r-1, c), (r+1, c), (r, c-1), (r, c+1)이다. 아..

문제 20057번: 마법사 상어와 토네이도 (acmicpc.net) 20057번: 마법사 상어와 토네이도 마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을 www.acmicpc.net 풀이 1 토네이도가 이동하며 흩뿌린 모래 중 격자 밖에 있는 모래양의 합을 출력해야 하므로, 보드 공간을 2만큼 양 옆 위 아래로 넓혀주면 편하다. 토네이도의 이동과 모래가 뿌려지는것을 구현하면 되고, 이는 마스킹과 같이 생각할 수 있다. 마스크 역할을 하는 토네이도는 반시계 방향으로 90도 돌릴필요가 있고, 두번 꺾을때 마다 이동거리가 1 씩 늘어난다. 종료조건에..

문제 크기가 N×M인 지도가 존재한다. 지도의 오른쪽은 동쪽, 위쪽은 북쪽이다. 지도의 좌표는 (r, c)로 나타내며, r는 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로부터 떨어진 칸의 개수이다. 가장 왼쪽 위에 있는 칸의 좌표는 (1, 1)이고, 가장 오른쪽 아래에 있는 칸의 좌표는 (N, M)이다. 이 지도의 위에 주사위가 하나 놓여져 있으며, 주사위의 각 면에는 1보다 크거나 같고, 6보다 작거나 같은 정수가 하나씩 있다. 주사위 한 면의 크기와 지도 한 칸의 크기는 같고, 주사위의 전개도는 아래와 같다. 2 4 1 3 5 6 주사위는 지도 위에 윗 면이 1이고, 동쪽을 바라보는 방향이 3인 상태로 놓여져 있으며, 놓여져 있는 곳의 좌표는 (1, 1) 이다. 지도의 각 칸에도 정수가 하나씩 있다...

문제 어른 상어가 마법사가 되었고, 파이어볼을 배웠다. 마법사 상어가 크기가 N×N인 격자에 파이어볼 M개를 발사했다. 가장 처음에 파이어볼은 각자 위치에서 이동을 대기하고 있다. i번 파이어볼의 위치는 (ri, ci), 질량은 mi이고, 방향은 di, 속력은 si이다. 위치 (r, c)는 r행 c열을 의미한다. 격자의 행과 열은 1번부터 N번까지 번호가 매겨져 있고, 1번 행은 N번과 연결되어 있고, 1번 열은 N번 열과 연결되어 있다. 파이어볼의 방향은 어떤 칸과 인접한 8개의 칸의 방향을 의미하며, 정수로는 다음과 같다. 7 0 1 6 2 5 4 3 마법사 상어가 모든 파이어볼에게 이동을 명령하면 다음이 일들이 일어난다. 모든 파이어볼이 자신의 방향 di로 속력 si칸 만큼 이동한다. 이동하는 중에..

문제 19237번: 어른 상어 (acmicpc.net) 19237번: 어른 상어 첫 줄에는 N, M, k가 주어진다. (2 ≤ N ≤ 20, 2 ≤ M ≤ N2, 1 ≤ k ≤ 1,000) 그 다음 줄부터 N개의 줄에 걸쳐 격자의 모습이 주어진다. 0은 빈칸이고, 0이 아닌 수 x는 x번 상어가 들어있는 칸을 의미 www.acmicpc.net 풀이 1 상어가 매번 이동할 때 마다 "냄새 값"이 1씩 줄어드는데, 어렵게 생각할 필요 없이, 매 초마다 모든 냄새 값을 1씩 빼준 뒤 상어가 위치하는 곳에 냄새 값을 K로 갱신해주면 된다. while 문 안에 들어가는 로직만 잘 설계하면 생각보다 어렵지는 않은 문제이다. import heapq # 북,남,서,동 dRow = [-1,1,0,0] dCol = [0,..