개발 일지

문제 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,..

문제 19238번: 스타트 택시 (acmicpc.net) 19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 풀이 1 문제에는 명시되어 있지 않지만, 각 손님의 출발지점은 다르지만 도착지점은 같을 수 있다. 처음에는 각 손님에 대해서 거리를 구해 heapq에 넣었지만, 시간초과가 발생한다. 택시의 위치부터 보드 전체를 탐색하며 남아있는 손님을 탐색하면 시간초과가 발생하지 않는다. 여러 제한 조건들을 유의해서 풀이해야하는 문제이다. from collections import d..

문제 19236번: 청소년 상어 (acmicpc.net) 19236번: 청소년 상어 첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 www.acmicpc.net 풀이 1 문제에서 상어가 물고기를 먹는 경우 중 번호의 합이 최대가 되는 경우를 구해야 하므로, 백트래킹으로 접근해야겠다는 판단이 가능하다. 또한 조건에서 물고기 번호는 유일하므로, 물고기의 정보는 리스트에 담아 인덱스로 식별할 수 있겠다. 백트래킹으로 접근하게 될 것이므로 재귀함수 형태로 문제에서 주어진 상황을 구현해야 한다. 구현하는 것은 두 가지로, 물고기를 이동시키는 것과 상어가 이..

문제 모노미노도미노는 아래와 같이 생긴 보드에서 진행되는 게임이다. 보드는 빨간색 보드, 파란색 보드, 초록색 보드가 그림과 같이 붙어있는 형태이다. 게임에서 사용하는 좌표 (x, y)에서 x는 행, y는 열을 의미한다. 빨간색, 파란색, 초록색 보드가 사용하는 좌표는 그 색으로 그림에 적혀있다. 모노미노도미노 게임 보드 이 게임에서 사용하는 블록은 타일 하나 또는 두 개가 가로 또는 세로로 붙어있는 형태이다. 아래와 같이 세 종류가 있으며, 왼쪽부터 순서대로 크기가 1×1, 1×2, 2×1 이다. 모노미노도미노 게임에서 사용하는 블록 블록을 놓을 위치를 빨간색 보드에서 선택하면, 그 위치부터 초록색 보드로 블록이 이동하고, 파란색 보드로 블록이 이동한다. 블록의 이동은 다른 블록을 만나거나 보드의 경계..

문제 17825번: 주사위 윷놀이 (acmicpc.net) 17825번: 주사위 윷놀이 첫째 줄에 주사위에서 나올 수 10개가 순서대로 주어진다. www.acmicpc.net 풀이 1 문제에서, 같은 칸에 동시에 여러개의 말이 중복해서 존재할 수 없다는 조건이 있다. 즉 말을 이동하기 전, 해당 말이 이미 도착했는지, 혹은 해당 말이 이동하려는 칸이 이미 점유 중인지 따져봐야한다. 말이 도착할 수 있는 칸의 종류는 총 세가지 이다. 첫째로 도착칸을 지나간 경우, 둘째로 일반칸에 도착하는 경우, 셋째로 파란칸에 도착하는 경우이다. 파란칸에 도착하는 경우 진행방향이 바뀌는 점을 유의해야한다. 말이 진행할 수 있는 루트는 총 네가지로 볼 수 있다. 시작 -> 일반 -> 도착 시작 -> 10 -> 도착 시작 -..

문제 17837번: 새로운 게임 2 (acmicpc.net) 17837번: 새로운 게임 2 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하 www.acmicpc.net 풀이 1 전체 보드의 크기는 최대 12^2 = 144인 반면, 주어지는 말의 개수는 최대 10개밖에 안된다. 따라서 이 문제의 경우, 주어진 제한조건에 따라 말의 데이터를 따로 배열에 넣어놓고 탐색하는 방법이 유효하다고 판단 가능하다. 문제에서 조건으로 생각해야하는 것은 보드 경계와 각 칸의 색깔이다. 조건에 의해 보드 경계 바깥으로 나가는 경우와 파란색 칸으로 가는 경우는 동일하게 취급되며, 앞 뒤..

문제 17779번: 게리맨더링 2 (acmicpc.net) 17779번: 게리맨더링 2 재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름 www.acmicpc.net 풀이 1 두 코드를 잘 비교해보자. N = int(input()) A = [[0]*(N+1)] sum_total = 0 for _ in range(N): li = [] for elem in map(int, input().split()): li.append(elem) sum_total += elem A.append([0] + li) def get_result(x,y,d1,d2): p_list = [0]*6 col..