차가운오미자님의 유리병

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 문제 이해 주사위의 움직임만 잘 정리하면 어렵지 않은 문제이다. https://chagaun-omija.tistory.com/273?category=867475 [백준] 23288번: 주사위 굴리기 2 https://www.acmicpc.net/problem/23288 23288번: 주사위 굴리기 2 크기가 N×M인 지도가 존재한다..

https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 문제 이해 처음엔 500*500 (맵사이즈) * 5 (테트로미노 종류) * 4 (돌리는 거) 를 다 해봐야 해? 라고 생각해서 기겁했던 문제이다. 다 방향벡터로 만들어서 해야하나? 생각했다가 그냥 5개 테트로미노들에 대해 모든 좌표를 적용해보자 하고, 두 번째 테트로미노까지 구현했다가, 이건 아닌데... 싶어서 인터넷 검색을 했다. 1번부터 4번 테트로미노까지는 DFS로 처리하면 되고, DFS로 ..

문제 이해 오랜만에 보는 DFS의 인자가 1씩 증가하는 경우가 아닌 문제였다. 어느 날 의뢰받은 업무를 할 것인지를 정하는 모든 경우의 수를 탐색하면 된다. 일단 DFS의 인자인 day는 현재 날짜이다. day에서부터 업무를 다시 재개할 수 있다. 즉, day가 6이면 6일자 업무부터 다시 선택할 수 있다는 것이다. profit은 현재까지 업무를 선택해서 얻은 수익이다. 아무튼, day서부터 다시 업무를 뽑을 수 있으므로 재귀부분에서 for문의 시작점이 day가 된다. 종료 조건이 조금 헷갈리는데, day > N+1 로 설정한 이유는, 만약 day == N이면 (예제1의 경우 7) N(7)일차 업무는 선택할 수 있으니까 선택할 수 있도록 재귀문으로 보내줘야 한다. 만약 day == N+1이면 N+1차부터..

https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 문제 이해 저번에 봤던 연구소3이랑 비슷하다. 근데 이번에는 3개의 벽을 세우는 것이다. 3개의 벽을 세울 곳을 지정한 후에, 그 상황에서 바이러스가 퍼지는 것을 구현하고, 바이러스가 퍼지지 않은 빈칸의 개수를 세면 된다. 벽 세울 3곳을 구하기 위해서 처음에 입력받을 때 빈 칸의 좌표들을 blank라는 배열에 저장해줬다. 바이러스 퍼지는 것 구현할 때 바이러스를 빨리 enqueue하기 위해서 virus라는 ..

https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 문제 이해 그냥 단순 시뮬레이션이라고 생각하면 된다. 단계도 깔끔하게 넘버링해서 줘서 그대로만 코드로 바꿔주면 된다. 그래도 조금 헷갈리긴 하는데, while문 안에서 현재 위치를 청소한다 지금 방향에서 왼쪽, 예를 들어 북쪽이면 서쪽, 서쪽이면 남쪽을 살핀다. 왼쪽으로 돌기를 4번 해준다. 그 중에서 청소가 안된 곳이 있으면 거기로 이동해주고, for문에서 break한다. 4번 다 돌았는데 다..

https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 문제 이해 숫자가 최대 11개 주어진다는 것은 연산자는 최대 10개라는 뜻이다. 연산자의 순서를 정하는 것이기 때문에 DFS를 이용해서 모든 경우의 수를 탐색하면 된다. 연산자의 개수가 정해져있으니까, 그 배열에서 하나씩 빼가면서 고르고, 다 고른 후에 계산을 해보면 된다. 곱셈, 나눗셈 우선이 아니므로 간단하게 앞에서부터 계산해주면 된다. ..

https://www.acmicpc.net/problem/14890 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 문제 이해 이 문제도 SWEA에 있는 문제이다. 근데 백준에 있는 문제가 더 친절한 것 같다. 예외상황을 더 정리를 잘해준 것 같다. 물론 그냥 내가 SWEA 를 볼 때 문제를 제대로 안읽었을 가능성도 있다.ㅎㅎ 아무튼, 그냥 이건 무식한 시뮬레이션 문제이다. 처음에 배열에다가 행, 열을 복사해서 같은 함수로 그 줄이 통과할 수 있는 줄인지 확인하려고 했는데, 복잡하게 꼬여서 그냥 행 체크, 열 체크 함수를 별도로 만들..

https://www.acmicpc.net/problem/14891 14891번: 톱니바퀴 총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴 www.acmicpc.net 문제 이해 예전에 SWEA에서 푼 문제랑 동일하다. 그래서 그리 어렵지 않게 풀 수 있었다. 문제를 제대로 읽으면 되는데, 사실 한 번 풀어봤던 문제라고 대충 읽었다가 오타를 엄청 내고 말았다. 일단 1. 톱니바퀴 a가 돌면 a+1 이나 a-1 은 반대방향으로 돈다 2. 극성이 다를 때 따라 돈다. 이 두 개를 살짝 헷갈렸다. 톱니바퀴는 친절하게 4개밖에 안주어진다. 그리고 날도 8개밖에 없다..

https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 문제 이해 역시 모든 경우를 탐색해야 하는 문제이다. CCTV의 최대 개수가 8개라고 하는 거부터가 그냥 DFS를 써라~ 하는 것 같다. CCTV는 다섯개의 종류가 있고, 1번, 3번, 4번의 경우 방향을 돌리면 4가지 경우의 수 2번의 경우 2가지 경우의 수 5번의 경우 1가지 경우의 수 가 있다. i번 CCTV가 j방향을 가리킬 때 동서남북 중 k방향을 감시할 수 있는지를 dir라는..

https://www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 문제 이해 사다리에 가로선들을 추가해보는 모든 경우를 탐색한다. 하지만 사다리는 최대 3개만 놓을 수 있어서, 3개를 넘게 놓는 경우는 패스해준다. 0개, 1개, 2개, 3개 놓는 경우 중 조건에 해당하는 경우가 되면 그 때의 추가한 사다리 개수에 따라 min값을 갱신해주면 되는 문제이다. map[i][j]는 j번 사다리에 j+1번으로 가는 (= 오른쪽으로 가는) 높이 i에 있는 사다리가 있다는..