차가운오미자님의 유리병

https://www.acmicpc.net/problem/20061 20061번: 모노미노도미노 2 모노미노도미노는 아래와 같이 생긴 보드에서 진행되는 게임이다. 보드는 빨간색 보드, 파란색 보드, 초록색 보드가 그림과 같이 붙어있는 형태이다. 게임에서 사용하는 좌표 (x, y)에서 x는 행, www.acmicpc.net 나머지 예제 생략 문제 이해 그냥 시뮬레이션을 돌리면 되는 문제이다. 처음에 저 맵을 그대로 만들어야 하나...? 했는데, 그냥 초록맵과 파랑맵을 만들어줬다. 빨간맵의 (y, x)에 블럭이 들어왔을 때, 파랑맵에는 y행에서 들어갈 수 있는 위치를 찾고 초록 맵에는 x열에 들어갈 수 있는 위치를 찾는다. 초록맵과 파랑맵에 고통으로 들어갈 수 있는 함수를 만드려고 했다가 너무 복잡해져서 그..

https://www.acmicpc.net/problem/19238 19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 문제 이해 1. 현재 택시의 위치에서 제일 가까운 손님 찾기 (BFS) 2. 손님을 태우고 도착지까지 최적 경로 찾기 (BFS) BFS를 하는 것은 명백한데, 구체적으로 하는게 좀 복잡하다. Find_Nearest_Customer() 모든 손님들에 대한 거리를 구해서 cus 배열에 넣어준다. 큐에 넣을 때는 남은 가스량과 거리를 함께 저장한다. 만약 가스가 ..

https://www.acmicpc.net/problem/19237 19237번: 어른 상어 첫 줄에는 N, M, k가 주어진다. (2 ≤ N ≤ 20, 2 ≤ M ≤ N2, 1 ≤ k ≤ 1,000) 그 다음 줄부터 N개의 줄에 걸쳐 격자의 모습이 주어진다. 0은 빈칸이고, 0이 아닌 수 x는 x번 상어가 들어있는 칸을 의미 www.acmicpc.net 나머지 예제 생략 문제 이해 큰 틀을 잡아보면, 1. 상어가 냄새를 남긴다 2. 상어가 이동한다 3. 겹치는 위치에 상어가 있으면 작은 상어만 남기고 다른 상어는 죽인다 4. 상어가 1번만 남았는지 확인한다 상어의 흔적을 남길 맵을 정의해야 하는데, 나는 smell_map과 no_map을 두었다. smell_map은 냄새의 수명이 저장되고, no_map..

https://www.acmicpc.net/problem/18808 18808번: 스티커 붙이기 혜윤이는 최근에 다양한 대회를 참여하면서 노트북에 붙일 수 있는 스티커들을 많이 받았다. 스티커는 아래와 같이 사각 모눈종이 위에 인쇄되어 있으며, 스티커의 각 칸은 상하좌우로 모두 연 www.acmicpc.net 나머지 예제 생략 문제 이해 정말 그냥 스티커를 붙이는 모든 경우를 생각하면 되는 문제였다. 붙여보고 안되면 다르게 붙여보고 이런식으로... 3단계이다. 1. 스티커를 붙여본다. 2. 그 모양으로 못붙이면 돌린다. 3. 4번 돌려봤는데 다 안됐으면 그 스티커는 버린다 Try_Stick() 모든 맵 칸에 대해서 그 칸이 스티커의 좌상칸이라고 생각하고, 그 칸에 붙여본다. 만약 붙이는데 맵에 이미 채워..

https://www.acmicpc.net/problem/17825 17825번: 주사위 윷놀이 주사위 윷놀이는 다음과 같은 게임판에서 하는 게임이다. 처음에는 시작 칸에 말 4개가 있다. 말은 게임판에 그려진 화살표의 방향대로만 이동할 수 있다. 말이 파란색 칸에서 이동을 시작하면 www.acmicpc.net 문제 이해 윷놀이 판을 어떻게 표현해야할지가 고민되었다. 출발부터 도착까지 가는 경로는 이렇게 5가지가 있으니까 이 경로들을 배열로 만들어주었다. 초록색 경로는 0번, 파란색 경로는 1번, 주황색 경로는 2번, 노란색 경로는 3번이다. 말은 초록색 경로의 10, 20, 30칸에 도착하면 r[0] 번 길에서 각 r[1], r[2], r[3]번 도로로 가게 된다. 그리고 4개의 말의 위치와 정보를 저..

https://www.acmicpc.net/problem/17822 17822번: 원판 돌리기 반지름이 1, 2, ..., N인 원판이 크기가 작아지는 순으로 바닥에 놓여있고, 원판의 중심은 모두 같다. 원판의 반지름이 i이면, 그 원판을 i번째 원판이라고 한다. 각각의 원판에는 M개의 정수가 적혀 www.acmicpc.net 나머지 예제 생략 문제 이해 원판을 배열로 생각하면 된다. Turn_Plate(): 방향에 맞춰서 해당되는 행을 회전시킨다. Erase_Duplicates(): 판(pan)의 모든 칸에 대해서 4방향 탐색을 한다. 만약 같은 숫자가 있으면 tmppan 배열에 -1이라고 표시를 해준다. 이때, 열의 끝이 연결되어 있으므로, 열의 범위를 벗어나면 다시 돌아서 행의 반대 끝이 되도록 한..

https://www.acmicpc.net/problem/17779 17779번: 게리맨더링 2 재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름 www.acmicpc.net 나머지 예제 생략 문제 이해 식 세우는데 한참 걸렸다. 좌표 이해 안하고 문제에 있는 설명만 복붙해서 풀려다가 한참 걸렸다. 그냥 처음부터 좌표를 볼 걸ㅎㅎ 예제 3을 보면 다음과 같이 생겼다. 노란색 칸은 모두 경계선이다. 내가 최종적으로 푼 방법은, 위와 같은 맵(tmp)을 하나 만드는 것이다. Draw_Map() 우선 노란색 경계선을 그린다. (그냥 문제에 있는 식에 맞춰서 그린다) 그런 후에, ..

https://www.acmicpc.net/problem/17281 17281번: ⚾ ⚾는 9명으로 이루어진 두 팀이 공격과 수비를 번갈아 하는 게임이다. 하나의 이닝은 공격과 수비로 이루어져 있고, 총 N이닝 동안 게임을 진행해야 한다. 한 이닝에 3아웃이 발생하면 이닝이 종 www.acmicpc.net 나머지 예제 생략 문제 이름이 ⚾ 라서 검색하기도 힘든 문제;;; 암튼 문제 이해 문제의 요점은, 10명의 선수의 순서를 정하고 (DFS) 이닝(행) 별 선수 성적(열)에 맞춰서 그 순서에서 얻을 수 있는 점수를 계산해서, 그 중 최대값을 찾아라 이다 DFS는 그리 어렵지 않게 짤 수 있고, 그 타순으로 시뮬레이션을 돌려보는게 좀 복잡한 부분이다. 나는 base라는 배열을 만들어서 각 베이스 별로 선수..

https://www.acmicpc.net/problem/16985 16985번: Maaaaaaaaaze 첫째 줄부터 25줄에 걸쳐 판이 주어진다. 각 판은 5줄에 걸쳐 주어지며 각 줄에는 5개의 숫자가 빈칸을 사이에 두고 주어진다. 0은 참가자가 들어갈 수 없는 칸, 1은 참가자가 들어갈 수 있는 칸을 www.acmicpc.net 문제 이해 문제가 매우 길고 어려워 보이지만 결국 DFS를 통해 모든 경우의 수를 탐색하는 문제이다. 5*5 판을 3번 회전시켜 총 4가지의 경우의 수가 있다. 이런 판이 5개가 있는데, 이걸 순서를 바꿔가며 쌓을 수 있다. 그리고 이렇게 쌓은 5*5*5의 정육면체에서 한 꼭짓점에서 마주보는 꼭짓점으로 가는 경로의 쌍이 4개가 존재한다 (정육면체 모서리는 8개니까) 즉, 총 ..

https://www.acmicpc.net/problem/11003 11003번: 최솟값 찾기 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net 문제 이해 구현보다는 수가 크기 때문에 아이디어를 내는 것이 조금 어려운 문제였다. 기본적으로 슬라이딩 윈도우를 써야겠다!고는 생각했으나, 잘 안되서 결국 인터넷 검색을 참고했다. 기본 C로는 배열을 이용해서 덱을 구현해야 할 것 같으나, C++을 써서 deque 라이브러리를 이용했다. deque(덱)은 queue와 달리 앞으로도 넣을 수 있는 구조이다. 덱에 숫자..