백준

문제 https://www.acmicpc.net/problem/20055 20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부 www.acmicpc.net 풀이 문제 지문이 워낙 이해하기 힘들었다. 심지어 이해를 잘못한 상태로 코드를 짜다가, 영 이상한 거 같아서 질문게시판에서 지문에 대한 설명을 조금 도움 받은 후 풀이했다. pypy3으로 통과했다. 난 총3개의 저장소를 사용해서 풀이했다. (deque) location[i] = i번째 위치에 존재하는 발판 location의 i는 위치적인 면을 나타낸다. 컨베이어는 계속 ..

문제 https://www.acmicpc.net/problem/17822 17822번: 원판 돌리기 반지름이 1, 2, ..., N인 원판이 크기가 작아지는 순으로 바닥에 놓여있고, 원판의 중심은 모두 같다. 원판의 반지름이 i이면, 그 원판을 i번째 원판이라고 한다. 각각의 원판에는 M개의 정수가 적혀 www.acmicpc.net 풀이 문제를 정말 잘 읽고, 하나하나 놓치지않고 구현하면 되는 문제다. 고려할점 몇가지, 데이터를 deque vs list 어디에 저장? 덱을 사용하면 rotate 함수가 있기에 회전은 쉽게 할 수 있다. 대신 덱은 접근연산이 O(n)이다. 반대로 리스트는 접근시간이 1인 대신, 회전할 경우 시간이 덱에 비해 훨씬 걸린다. 그러나 내가 생각한 풀이는 회전횟수보다는 인덱스에 접..

문제 https://www.acmicpc.net/problem/21608 21608번: 상어 초등학교 상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호 www.acmicpc.net 풀이 우선 입력값을 1차원 배열에 저장하고, 학생번호로도 접근할 수 있도록 딕셔너리에도 세팅해둔다. 그 다음은 2차원 배열을 모두 돌면서 어느자리가 적합한지를 판단해야한다. 선호하는 친구의 수, 빈칸의 공간을 매 칸마다 확인하며, 이전에 저장한 최댓값보다 크다면 갱신해주고 아니라면 넘어가면 되는 식으로 구현하면 된다. 단, 귀찮은 부분이 있는데 친구도, 빈칸도 같을때이다. 이 때는..

문제 https://www.acmicpc.net/source/62767025 로그인 www.acmicpc.net 풀이 해당 문제는 자기 위에 올라가있는 친구들을 어떻게 잘 관리하는지가 핵심인데, 덱을 사용하면 손쉽게 관리할 수 있다. 예로 다음칸이 흰색이고 순서가 3일 경우를 보자. (배열 왼쪽이 낮은 위치) [2, 3, 1, 4] , [5, 6] 이라고 할 경우 [5, 6, 3, 1, 4] 가 되어야한다. 이 과정은 덱을 활용해서 [2, 3, 1, 4] 에서 뒤에서부터 4, 1, 3 을 순서대로 pop하고, 임시 덱에 pop한 값을 왼쪽부터 넣으며 [3, 1, 4] 로 만들 수 있다. 빨간 칸은 더 쉽다. [2, 3, 1, 4], [5, 6] => [5, 6, 4, 1, 3] 를 만들어야하는데 중간에 ..

문제 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/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배열을 기준으로 방향을 저장했고, 이렇게 방향이 저장된 배열은 바람이 불 때 사용했다. 다음은 미세먼지의 확산 함..