개발 일지

문제 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]*(..

문제 Softeer Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai 풀이 정말 오랜만에 c++로 풀이하느라 애를 많이 먹었다. 문제 자체는 정말 쉬운데, 회의실 이름을 키 값으로 하고 스케쥴 상 비어있는 시간을 pair로 가지고 있는 vector를 값으로 map을 만들어준뒤, 예약 시간이 입력될 때마다 해당 회의실의 가능한 시간을 갱신해나가면 된다. 새로 vector를 만들어서 pair를 넣어줘서 map의 value가 새로 생성된 pair를 가리키게 하면 되겠다. 다만 c++은 사용하지 않는 vector는 메모리 해제를 직접 해줘야 하는데, 파이썬의 편리함에 물들어 까먹고 그냥 제출해버렸다... 어쨌거나 맞았으니 다행. 다음은 문제를 풀며 참고한 c++ 문법 레퍼런스이..

문제 Softeer Softeer 자율주행차가 아래와 같은 교차로를 통과하는 상황을 생각하여 보자. 이 문제에서 다루는 교차로에서는 직진만 가능하기 때문에, 아래 그림과 같은 네 가지 방법으로만 교차로 softeer.ai 풀이 N만큼 반복문을 돌며 교차로에 새로 들어서는 차량의 도착 시간 및 방향을 입력받아 입력된 차량들이 교차로를 지나간 시간이 어떻게 되는지 출력하는 문제이다. 따라서 시간의 흐름에 따라 교통상황이 어떻게 흘러가는지 면밀하게 살펴 문제에 접근할 필요가 있다. 시간의 흐름을 구현하는것이 핵심이며, 새로 차량 정보가 입력되면 그 이전 시점까지의 교통 상황을 정리하면 된다. 1초 동안, 만약 차량들이 서로 마주보고 있다면 동시에 지나갈수 있고 그렇지 않다면 오직 하나의 차량만 지나갈 수 있다..

문제 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)이다. 아..