출처 : 백준, https://www.acmicpc.net/problem/14890 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net # NxN의 지도가 주어진다 # 모든 칸의 높이가 같으면 길 # 길이가 다른 경우에는 경사로를 놓아서 길을 만들 수 있다. # 경사로의 높이는 항상 1이고 높이는 L # 경사로는 낮은 칸에 놓고, L개의 연속된 칸에 모두 접해야함. # 경사로의 낮은 칸과 높은 칸의 차이는 1이어야한다. # 경사로를 놓을 낮은 칸의 높이는 모두 같아야하고, L개의 연속된 칸이 있어야함. # 지나갈 수 있는 길의 갯수 더보..
출처 : 백준, https://www.acmicpc.net/problem/20056 20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치 www.acmicpc.net # n x n의 격자, m개의 파이어볼 # 1:n은 연결되어있다 # 파이어볼은 r, c, m, d, s의 정보로 주어진다 # 1 ≤ ri, ci ≤ N -> 1부터 시작함. # d는 0~7까지 12시 기준 시계 방향 8방향, s는 한번 움직이는 칸 수 # 이동이 모두 끝나고, 2개 이상의 파이어볼이 같은 칸에 있다면 # 모두 합친 후 4개로 ..
출처 : 백준, https://www.acmicpc.net/problem/17140 17140번: 이차원 배열과 연산 첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100) 둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다. www.acmicpc.net # 배열의 크기는 3 x 3 # 정렬은 1초마다 빈도 -> 숫자 순으로 오름차순 정렬하되 [숫자, 빈도, 숫자, 빈도, ...] 꼴로 새로운 배열은 만듬 # 정렬 시 0은 세지 않음 # 행의 개수와 열의 개수를 비교해서 행이 같거나 크면 행을 기준으로, 열이 크면 열을 기준으로 정렬 # 길이가 다를 경우 가장 긴 배열을 기준으로 모자란 길이를 0으로 채움 # 길이가 1..
출처 : 백준, https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net # 1초 동안 # 미세먼지가 모든 칸에서 동시에 확산 # 인접한 네방향으로 그 칸 // 5만큼 확산 # 확산시킨 칸의 미세먼지는 원래 미세먼지 - (원래 미세먼지 // 5) * 확산한 방 수 # 공기청정기가 있거나 칸이 없다면 확산 X # 공기 청정기 작동 # 위쪽은 반시계, 아랫쪽은 시계 방향으로 미세먼지가 한 칸 씩 이동 # 공기 청정기는 1열(0)에 있고 2칸을 차지하며 -..
출처 : 백준, https://www.acmicpc.net/problem/15685 15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커 www.acmicpc.net # 다음 세대 드래곤 커브 # 이전 세대 드래곤 커브의 끝 점을 기준으로 90도 시계 방향 회전 # 그것을 끝 점에 붙인 것임 # 격자 위에는 N개의 드래곤 커브가 존재 # x, y, d, g # 1x1 크기의 정사각형의 꼭짓점이 모두 드래곤 커브의 일부인 정사각형의 개수 더보기 먼저, 생각해야 할 부분 1. 꼬마신 신고 평행 이동과 회전 변환, 잊지 않..
출처 : 백준, https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net # 1번 1방향 # 2번 서로 반대 방향 # 3번 서로 직각 # 4번 3방향 # 5번 4방향 # CCTV는 벽을 넘을 수 없으나, CCTV는 넘을 수 있다. # 최소 사각지대의 개수 더보기 먼저, 생각해야 할 부분 1. 여러개의 CCTV가 바라볼 수 있는 모든 방향에 대한 조합을 어떻게 구할지 생각해본다. 풀이 모든 조합을 훑어 최소값을 알아보고 싶다면, 깊이 우선 탐색..
출처 : 백준, https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net # 한 칸에 한나라, 인구이동은 하루에 한 번 # 인구 이동이 발생하지 않을 때 까지 반복 # 두 나라 사이의 인구 차가 L 이상 R 이하이면, 국경선 OPEN # 국경선을 모두 연 다음에 인구 이동 시작 # 국경선이 열린 나라들끼리 연합 # 인구 이동 = 연합 인구 / 연합 이루는 나라 수 (소수점 버림) # 인구이동이 발생한 일자 더보기 먼저, 생각해야 할 부분 ..
출처 : 백준, https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net # 벽을 3개 세울 수 있다. # 바이러스는 상하좌우로 퍼져나간다 # 바이러스가 있는 칸은 연구소 내에 2개 이상 9개 이하이다. # 안전영역의 최댓값을 구하여라 더보기 먼저, 생각해야 할 부분 1. 어떻게 해야 벽을 세울 칸을 효율적으로 선택할 수 있을지 고민해보자. 아마.....없을 것이다. 벽을 세울 칸을 효율적으로 선택할 수 없다면...다 해봐야지 어쩌겠니... 2. 그렇다면 안전 영역..
출처 : 백준, https://www.acmicpc.net/problem/14499 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 더보기 먼저, 생각해야 할 부분 1. 주사위를 굴리는 알고리즘 문제의 핵심은 주사위를 굴리는 알고리즘을 어떻게 구현할 것인가이다. 주사위의 면과 적혀있는 숫자를 매칭하는 것과, 실제 놓여진 주사위의 각 면의 방향과 주사위의 각 면을 매칭하는 것을 따로 생각해보자. 괜히 주사위의 각 면에 번호를 붙여준게 아니다. 풀이..
출처 : 백준, https://www.acmicpc.net/problem/3190 더보기 먼저, 생각해야 할 부분 1. 계속 움직이는 뱀이 차지하는 좌표들을 어떻게 관리하면 좋을까? 뱀이 자기자신에게 부딪혀도 게임 오버이기 때문에 지속적으로 뱀의 좌표를 관리해주어야한다. 뱀이 한 번 움직일 때마다 뱀이 차지하는 좌표들을 조회해야했기 때문에 빠르게 조회할 수 있는 자료형이 필요했고, 처음에는 좌표들을 set에 넣어서 관리하려고 했다. 이를 통해 새 좌표를 넣어주고, 꼬리를 제거하면서 필요 시 간편하게 조회할 수 있을 것이라 생각했다. 그러나 set은 성분의 순서를 보장하지 않기 때문에 뱀의 꼬리가 어디인지 알아낼 수 없었다. 이를 해결하기 위해 dictionary 자료형을 사용하도록 변경했다. (Pytho..
출처 : 백준, https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 더보기 먼저, 생각해야 할 부분 1. 1개를 골랐을 때 최대 m개라면, m개를 골랐을 때도 같은 값이 나온다. m개가 최댓값이라면 m개를 골랐을 때 최댓값이 나온다. 최대 m개를 골라야하지만, 어짜피 m개보다 작게 고른 경우의 수가 m개를 뽑았을 때도 포함되어 있으므로, 1~m개를 모두 계산하는게 아니라 m개를 고른 경우에 대해서만 계산하면 된다. 풀이 def..
출처 : 백준, https://www.acmicpc.net/problem/21610 21610번: 마법사 상어와 비바라기 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기 www.acmicpc.net 더보기 먼저, 생각해야 할 부분 1. 문제를 단순하게 줄여보자 # 구름은 d방향으로 s칸만큼 이동 후 구름이 있는 칸의 물 + 1 => 구름 제거 # 물이 증가한 칸에 대각선 방향으로 거리가 1인 바구니 중 물이 있는 바구니 수만큼 바구니만큼 물 증가 # 1, N 경계는 취급 X # 바구니에 저장된 물의 양이 2 이상인 모든 칸에 구름이 생기고 물의 양이 2가 줄어듬. # ..
