whiporithm

문제 https://www.acmicpc.net/problem/17779 17779번: 게리맨더링 2 재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름도 www.acmicpc.net 풀이 구현.. 그냥 싹 다 구현인 문제다. 나처럼 풀이하는게 맞는 방법인지는 모르겠으나, 섬세하게 코드 짜지않으면 바로 틀려버리는 문제.. 문제 같은 경우에는 d1과 d2이 가질 수 있는 모든 경우의 수와, 기준점이 될 수 있는 점의 좌표를 넣어 하나씩 모두 계산해본다음 최솟값을 찾는 방식으로 접근했다. 초반에 탐색 시간을 조금이라도 더 줄여볼려고, 짜잘한 테크닉을 썼다. 조건과 예시 사진의 형..

문제 https://www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고, www.acmicpc.net 풀이 조합과 bfs로 풀이할 수 있는 문제다. 1. 우선 바이러스 있는 위치의 조합을 모두 구한다. 2. 조합을 돌면서 bfs를 수행한다. 3. 최솟값을 구한다. 대략적인 풀이는 이러한데 중요한 부분이 있다. 목표가 모든 칸의 바이러스 점령이므로, 비활성 바이러스를 꼭 활성화 해줄 필요는 없다. '비활성 바이러스' 그 자체도 바이러스기 때문에 정확한 목표는 주어진 입력값에서 0 부분이 모두 바이러스..

문제 https://www.acmicpc.net/problem/17143 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net 풀이 전형적인 시뮬레이션, 구현 문제 2차원 배열을 선언해주고 상어가 있는 위치에 [크기, 방향, 시간] 을 저장했다. 1차적으로 낚시왕의 열에서 행이 가장 작은 상어를 먹는다. 그리고 상어가 이동한다. 이 때 결과값을 저장할 빈 2차원 배열을 선언해둔다. 기존의 상어가 저장된 2차원 배열을 돌면서 상어가 존재하는 위치라면 저장해놓은 방향을 통해 한칸씩 이동한다. 만약 벽..

문제 https://www.acmicpc.net/problem/17140 17140번: 이차원 배열과 연산 첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100) 둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 해당문제의 핵심요소는 1. 배열의 크기를 어떻게 늘리느냐 배열의 크기 같은경우에는 늘리지말고, 최대치를 선언한다음에 바운더리를 정해주는 식으로 해결하면 된다. 초기값은 3, 3이고, 연산에 따라 행이나 열의 사이즈를 늘리면 된다. 2. 정렬을 어떻게 할 것인가 정렬 같은경우에는 우선 최소힙을 사용해서 수와, 수가 카운트 된 횟수를 체크한다. ex> [2, 2, 1, 4] 면..

문제 https://www.acmicpc.net/problem/13458 13458번: 시험 감독 첫째 줄에 시험장의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 각 시험장에 있는 응시자의 수 Ai (1 ≤ Ai ≤ 1,000,000)가 주어진다. 셋째 줄에는 B와 C가 주어진다. (1 ≤ B, C ≤ 1,000,000) www.acmicpc.net 풀이 dp로 풀었다. 우선 총 감독관이 커버할 수 있는 경우는 모두 1명으로 초기화 했고, 이후에 +c명까지 부감독관 한명씩 늘려주면 된다. 범위 체크만 잘해서 입력값의 한계까지 구한다음, dp배열에 접근하여 값만 더해주면 된다. 코드 from sys import stdin n = int(input()) a = list(map(int,..

문제 https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 풀이 아무리봐도 너무 삽질처럼 푼 거 같아 풀이이후에 검색해보니 대부분 bfs 방식으로 문제를 풀었더라. 나만 dfs로 하드하게 풀었다... 나 같은 경우에는 이동하기전에 이동경로에 다른 볼이 있는지 먼저 검사했다. B...R.. 같은 경우나 BR.. 같은 경우등을 고려한 조건이었고, 빨간 구슬을 기준으로 경로에 파란 구슬이 있다면, 파란 구..

문제 https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 풀이 열심히 열심히 구현하면 되는 문제다. 먼지 확산관련해서 조금 헷갈렸는데, 확산되는 먼지값들은 모두 합쳐주면 되는거였다. 나는 함수들을 몇개 나눠서 구현했다. 우선 공기청정기를 기준으로 바람이 부는 방향을 다 저장하는 함수를 만들었다. 해당 방향은 내가 지정해놓은 dx, dy배열을 기준으로 방향을 저장했고, 이렇게 방향이 저장된 배열은 바람이 불 때 사용했다. 다음은 미세먼지의 확산 함..

문제 https://www.acmicpc.net/problem/16235 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net 풀이 요구사항 같은 경우에는, 크게 설명할 게 없다. 각 칸마다 1개 이상의 나무들을 저장할 수 있는 리스트와, 양분을 저장할 수 있는 저장 공간을 만들어둔다. 이후 봄, 여름, 가을, 겨울 로직을 순서대로 실행한다. 봄에서 특정칸의 나무들을 모두 체크할 때, 만약 현재 양분으로 나무들을 못주면 죽는 나무로 처리한다. 그리고 양분을 줄 수 있는 나무중 5의 배수인 나무의 위치..

문제 https://www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 풀이 시간제한이 굉장히 빡센 문제로, 오랫동안 고민한 문제다. 내가 처음 풀이했던 방식은 다음과 같다. 우선 입력을 모두 받고 아래와 같은 형식으로 2차원 배열을 저장한다. '#' 은 내가 움직일 수 있는 가로선과 세로선을 의미한다. 이후에 사다리를 0개, 1개, 2개, 3개 놓는 모든 상황을 dfs로 만들어주고 탐색을 시작한다. 단 가로선이 연속되지 않도록 검사하면서 놓아주어야 한다. 탐..

문제 https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 풀이 완탐 + 구현문제이다. 첫번째로 cctv 종류와 cctv위치를 배열에 저장한다. 다음으로 cctv별로 회전할 수 있는 경우의 수를 모두 구한다. 나는 일관성을 가지기 위하여 모두 4방향으로 회전한다고 가정했으며 [ 0, 1, 2, 3 => 우, 하, 좌, 상 ] 순으로 정의했다. 이 때 itertools product를 통하여 모든 경우의 수를 만들었다. 마지막으로 3차원 배..