차가운오미자님의 유리병

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에 있는 사다리가 있다는..

https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 문제 이해 음~ 쉽다 해놓고 이상한 오타내고서 헤맨 문제...ㅎㅎ 최대 20명을 두 팀으로 나누고서 점수 계산만 하면 되니까, 두 팀으로 나누는 게 핵심인 문제이다. 두 팀으로 나눈다 -> 선택 10명 vs 비선택 10명 이렇게 나누면 되겠다! 그러면 DFS로 10명을 고르는 조합을 구해주면 되겠다! 작성 코드 #include #include #define MAXN 20 #define ABS(x) (((x)>0)? (..

https://www.acmicpc.net/problem/15685 15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커 www.acmicpc.net 문제 이해 이걸 대체 어떻게 그림을 그려야하지 싶어서 바로 검색을 했다. 이 드래곤 커브는 패턴을 가지고 있다. 예를 들어 처음 방향이 0이면 0세대: 0 1세대: 0 1 2세대: 01 21 3세대: 0121 2321 4세대: 01212321 23032321 .... 로 이어진다. 즉 1세대는 0세대 커브 + 0세대 커브를 역으로 읽으며 거기에 1을 더한 값이다 ( 01..

https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 문제 이해 시간 초과 때문에 조금 애먹었던 문제이다. 심지어 처음에 너무 어렵게 접근해서 무슨 DFS + BFS로 풀었다... -> 당연 시간 초과 치킨집과 집 간의 거리는 그냥 수식으로 계산해야한다. 그리고 이걸 순열로 풀면 시간초과에 걸린다. 반드시 조합으로 해야한다. 이걸 알면서도 나는 순열로 풀고 있었다. ㅎㅎ... DFS에 idx를 추가해서 순열로 바꿔줬더니 바로 통..

https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 문제 이해 1. 국경을 열었다가 (만약 열린 국경이 하나도 없으면 더이상 조정이 일어나지 않으므로 끝낸다) 2. 연합국을 찾고 (모든 칸이 visit될 때까지 BFS) 3. 연합국 인구 평균을 연합국 모든 칸에 넣어주고 (만약 변경이 하나도 없으면 끝낸다) 4. 국경을 닫는다 Open_Border() 국경을 여는 것은 모든 칸에 대해 4방향 탐색을 하고 인구 차가 범위 내이면 ope..

https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 문제 이해 다른 상어가 물고기를 먹는 문제들보다 훨씬 간단하다. 일단 물고기 배열을 따로 만들지 않아도 된다는 점! 그냥 입력받은 맵으로만 처리가 가능한다. 1. 상어가 먹을 수 있는 물고기의 좌표를 찾는다 -> BFS 2. 만약 먹을 수 있는 물고기가 없다면 종료한다. 3. 찾은 좌표에 물고기 없애고 상어 넣고, 시간(t)에 상어 위치에서 그 물고기까지의 거리를 더한다. 4. 상어의 사이..

https://www.acmicpc.net/problem/17140 17140번: 이차원 배열과 연산 첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100) 둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다. www.acmicpc.net 문제 이해 행 연산과 열 연산은 어차피 행, 열만 바꾸면 같은 과정이므로 행 연산만 설명하도록 한다. 행 연산 ( R_Sort() ) y행에 대한 연산을 한다고 할 때, y행에 있는 모든 원소를 순회하면서, tbl[원소]++ 을 해줘서 숫자 별 개수를 tbl에 저장한다. 그럼 이제, 숫자 별 개수가 tbl에 저장되었으니까, tbl의 1부터 100까지, 1개 이상 존재하는 숫자를 구조체..

https://www.acmicpc.net/problem/17837 17837번: 새로운 게임 2 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하 www.acmicpc.net 문제 이해 디버깅하는데 한참 걸린 문제였다. 근데 오래 걸린 이유가 애초에 처음 주어진 예제를 제대로 안살폈기 때문이다. 적어도 저렇게 문제에 친절하게 그림을 그려줬으면, 거기까지는 내 맵이 잘 맞아 떨어지는 지를 먼저 좀 보자!!! 말을 움직이는 게 힘든 문제이다. 말 구조체를 struct { int y, x, d; int idx; // 현재 위치의 밑으로부터 몇 번째인지 } 이렇게 정의했다..

https://www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 문제 이해 푸는 방식도 쉽게 생각해낼 수 있고, 심지어 그냥 지나칠 수 있는 여러 예외 케이스들을 예제로 줘서 문제 푸는데 어려움이 없는 문제였다. 예제 6과 같이, 어떻게 선택하든 모든 빈 칸에 바이러스를 채우지 못하는 경우 예제 7과 같이, 처음부터 모든 칸에 바이러스가 있는 경우 를 고려해야 한다. 결론부터 말하자면 vcnt개의 바이러스 중에 M개를 선택(DFS)해서 이 M개 바이러스 위치에서 모든 ..