개발 일지

문제 17822번: 원판 돌리기 (acmicpc.net) 17822번: 원판 돌리기 반지름이 1, 2, ..., N인 원판이 크기가 작아지는 순으로 바닥에 놓여있고, 원판의 중심은 모두 같다. 원판의 반지름이 i이면, 그 원판을 i번째 원판이라고 한다. 각각의 원판에는 M개의 정수가 적혀 www.acmicpc.net 풀이 간단한 구현 문제지만, 각 행이 큐로 되어있어 인접 노드를 탐색할 때 주의해야한다. 어이없게도 "배수"를 반복문을 통해 2배씩 곱해주는 것으로 계산해서 많은 시간을 날렸다. 또한 평균을 구할 때 cnt 가 0이 되는 때도 있음을 주의해야한다. from collections import deque N,M,T = map(int,input().split()) # 0:W 1:R 2:B circ..

문제 15686번: 치킨 배달 (acmicpc.net) 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 풀이 사다리 조작 문제와 동일한 조합 문제이다. 치킨집을 최대 M개 까지 남길 수 있고, M개 이하의 가능한 조합을 짜보면서 최소가 되는 도시 치킨 거리를 갱신한다. 치킨집은 최대 13개, 가정집은 최대 2N개 까지만 존재할 수 있으므로 따로 좌표를 리스트에 넣어놓고 1차원 리스트에 대해 조합을 짜도 된다. N,M = map(int,input().split()) board = [[0]*(..

문제 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) 이다. 지도의 각 칸에도 정수가 하나씩 있다...