본문 바로가기

알고리즘/백준56

[백준 15684] 사다리 조작 (C++) A. 문제설명 https://www.acmicpc.net/problem/15684 문제에 대한 자세한 설명은 링크 참조 1. N개의 세로선과 M개의 가로선이 주어짐 2. 각 세로선에는 H개의 가로선을 놓을 수 있는데, 이는 좌표의 Y축 좌표에 해당된다고 이해하면 된다. 3. 주어진 가로선 이외에 가로선을 전체에서 추가로 3개까지 사용하여, i번째 사다리의 출발점이 i번째 도착점에 도달하도록 사다리를 조작 4. 조작에 추가 가로선이 3개 넘게 필요하다면 -1 반환, 그 이하면 그 갯수 반환 B. 접근법 DFS + 시뮬레이션 1. DFS: 0~3개까지 가로선 놓는 조합 구하기에 사용. 가로선을 추가로 놓는 조합에 대해서는 완전 탐색이 필요하고 해당 조합을 만드는 건 DFS를 사용하자. 2. 시뮬레이션: 가로.. 2020. 5. 8.
[백준 16235] 나무 재테크 (C++) A. 문제설명 https://www.acmicpc.net/problem/16235 문제에 대한 자세한 설명은 링크 참조 1. N * N 배열이 존재, 해당 배열 위에 나무를 키움 2. 매년 봄에는 나무가 각 자리에서 양분먹고 나이 1 증가, 양분이 부족하면 나무는 죽는다.(양분은 나이 적은 순부터 먹음) 3. 여름에는 죽은 나무가 해당 자리에 나이/2 만큼 양분이 됨 4. 가을에는 나무의 위치에서 인접한 8칸이 번식, 이때 5배수의 나이를 가진 나무만 해당함 5. 겨울에는 배열의 각 칸에 양분 추가 6. 최종적으로 K년 뒤의 나무의 총 개수 구하기 B. 접근법 시뮬레이션 문제의 풀이 자체는 어려울 것이 없으나 조건이 이것저것 여러가지 붙어있어 구현할 때 문제를 제대로 이해하지 않으면 실수하기 쉬운 유형이.. 2020. 4. 24.
[백준 14500] 테트로미노 (C++) A. 문제설명 https://www.acmicpc.net/problem/14500 문제에 대한 자세한 설명은 링크 참조 1. N * M 크기의 배열이 존재 2. 배열 위에 5개 종류의 테트리스 도형(테트로미노) 하나를 놓으려고 함 3. 테트로미노는 회전하거나 대칭시킬 수 있다. 4. 각 배열에 엔트리에 숫자 값이 존재하는 데 특정 위치에 이 테트로미노 하나를 놓아 최대의 합을 갖게 하는 경우 출력 B. 접근법 완전탐색과 시뮬레이션 먼저 이 문제에 대해 접근하려면 A. 문제설명의 3번 조건을 고려하여야 한다. 나의 경우 테트로미노의 4방향 회전과 대칭된 도형의 모양을 고려하여 구현하였고, 매 좌표를 탐사할 때 위와 같이 각각의 테트로미노 도형에 대해서 4방향을 회전한 경우의 영역의 엔트리 값의 합을 계산한.. 2020. 4. 12.
[백준 16234] 인구 이동 (C++) A. 문제설명 https://www.acmicpc.net/problem/16234 문제에 대한 자세한 설명은 링크 참조 1. N * N 배열 크기의 각 국가에 국민들 수가 주어짐 2. 각 인접한 칸의 국민 수의 차가 L이상 R이하일 때, 두 나라의 국경선을 염 3. 위 조건에 의해 국경을 열어 연합이 인구이동을 하게 될 때, 연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)가 된다. 4. 각 국가는 인구이동을 가능한 한 최대한 진행한다. 5. 이때 최대로 이루어질 수 있는 인구이동의 횟수를 반환 B. 접근법 시뮬레이션 문제. 문제상의 조건으로 2000 이상의 이동이 이루어지지 않는 입력만 들어온다고 했으므로, 문제의 내용을 충실하게 구현하여 그대로 적용할 수 있.. 2020. 4. 10.
[백준 15683] 감시 (C++) A. 문제설명 https://www.acmicpc.net/problem/15683 문제에 대한 자세한 설명은 링크 참조 1. N * M 배열 크기의 사무실에 K개의 CCTV가 설치 2. 배열의 각 좌표에는 0: 빈칸, 1~5: CCTV, 6:벽이 주어짐 3. 각 CCTV는 아래와 같이 번호에 따라 감시할 수 있는 방향이 정해져 있다. 4. CCTV는 같은 CCTV를 통과할 수 있으며, 벽은 통과하지 못한다. 5. CCTV는 90도씩 회전이 가능하며 전방향중 가장 감시면적이 넓은 방향을 보게할 때, CCTV가 감시하지 못하는 사각지대 영역의 최소 구하기 B. 접근법 완전탐색과 시뮬레이션 먼저, CCTV의 모든 방향 조합을 구하고, 그 조합에 따라 구해지는 사각지대 영역을 계산하여 그 중 최소를 고르자 C... 2020. 4. 10.
[백준 15686] 치킨 배달 (C++) A. 문제설명 https://www.acmicpc.net/problem/15686 문제에 대한 자세한 설명은 링크 참조 1. N * N 배열 크기의 도시가 존재 2. 배열의 각 좌표에는 0: 빈칸, 1: 집, 2: 치킨집이 존재 3. 각 집에서 가장 가까운 치킨집의 거리를 '치킨거리'라고 하는데, 이는 |r1-r2| + |c1-c2|로 구한다. 4. 여기서, 주어진 치킨집 중 M개의 치킨집만을 남기고 폐업하려고 하는데, 그 조건은 남은 M개의 치킨집이 도시의 모든 집들의 치킨거리가 최소가 되는 경우이다. 5. M개의 치킨집을 살렸을 때 도시의 최소치킨거리를 구할 것 B. 접근법 먼저 이 문제에서 내가 생각한 방식은 DFS이다. M개의 치킨집을 살리는 것에 대한 조합을 DFS로 모두 구해야하고, 그 조합을.. 2020. 3. 28.
[백준 15685] 드래곤 커브 (C++) A. 문제설명 https://www.acmicpc.net/problem/15685 문제에 대한 자세한 설명은 링크 참조 1. 시작점, 방향, 진행세대 수로 정의되는 드래곤 커브가 존재 2. 각 드래곤 커브는 시작점에서 시작해서 출발방향으로 이동하고, 세대의 진행에 따라 이전 세대의 드래곤 커브를 90도 회전시킨 후 끝점에 이어붙여서 확장 3. 주어진 세대로의 확장이 완료된 후 전체 좌표평면 내 드래곤커브가 걸쳐져 있는 사각형의 갯수 계수 이제 이걸 어떻게 그려야하나... 그림을 그려서 풀어야 할까? B. 접근법 처음 이 문제를 받아보고 생각이 든 것은 드래곤 커브 자체의 그림에 대한 생각이었다. 그러나, 이 문제에서 집중해야 할 것은 그림 자체가 아니라 규칙성이다. 각 세대별로 이전 세대의 특징을 가지고.. 2020. 3. 28.
[백준 5373] 큐빙 (C++) A. 문제설명 https://www.acmicpc.net/problem/5373 문제에 대한 자세한 설명은 링크 참조 1. 3 * 3 정육면체의 큐브가 존재 2. 큐브의 각 면에는 위:흰색, 아래:노란색, 앞:빨간색, 뒤:오렌지색, 왼:초록색, 오른:파란색으로 색칠됨 3. 큐브를 돌리는 횟수와 돌리는 면 및 방향(시계/반시계)이 주어짐 4. 주어진 대로 큐브를 모두 돌리고 난 후 윗면 9개 칸의 색상을 출력 문제의 조건은 사실 간단하다. 3 * 3 정육면체 루빅스 큐브를 구현하여 모사하면 되는 것 B. 접근법 큐브를 6개의 3*3 배열로 나누어 좌표에 유의하여 구현한다. 면의 회전방향이 보는 각도에 따라 달라지며 우리가 정의하는 X, Y의 좌표가 뒤집어진 면에서는 그에 맞추어야 하므로 전개도를 그려 헷갈.. 2020. 3. 12.
[백준 17144] 미세먼지 안녕! (C++) A. 문제설명 https://www.acmicpc.net/problem/17837 자세한 설명은 링크참조 1. R * C 칸의 방에 미세먼지 양 정보가 주어짐 2. 동시에 공기청정기 위치 (r, c)도 주어짐. 공기청정기는 세로 2칸 크기 3. 매 초마다 미세먼지 확산과 공기청정기 작동이 일어남 4. 미세먼지가 인접한 네 방향으로 확산 4-1. 공기청정기가 있거나, 벽이면 그 방향으로는 확산 X 4-2. 확산되는 양은 먼지량/5이고 소수점은 버린다. 4-3. 기존 칸에 남은 미세먼지의 양은 '먼지량 - (먼지량/5) * (확산된 방향의 개수)' 5. 공기청정기 작동 5-1. 위쪽은 반시계, 아래쪽은 시계방향으로 벽을 타고 공기이동 5-2. 먼지는 바람의 방향대로 한 칸씩 이동. 바람은 먼지없는 바람이고,.. 2020. 3. 5.
[백준 17140] 이차원 배열과 연산 (C++) A. 문제설명 https://www.acmicpc.net/problem/17140 자세한 설명은 위 링크에서 1. 3 * 3 배열이 존재 2. 배열에 매 초마다 연산을 적용 2-1. R 연산: 배열 A의 모든 행에 대해서 정렬을 수행한다. 행의 개수 ≥ 열의 개수인 경우에 적용 2-2. C 연산: 배열 A의 모든 열에 대해서 정렬을 수행한다. 행의 개수 < 열의 개수인 경우에 적용 3. 여기서 정렬의 의미는 각 행 또는 열 내 숫자들을 계수, 숫자들이 발생한 횟수를 조건에 맞추어 정렬한다는 것 * [1, 1, 2, 3, 3] 의 배열이 존재한다고 가정. 1이 2개, 2가 1개, 3이 2개이므로 [1, 2, 2, 1, 3, 2]의 새로운 배열을 만듦 4. 새로 만든 배열은 아래와 같이 정렬됨 4-1. 등장.. 2020. 3. 5.
[백준 17837] 새로운 게임 2 (C++) A. 문제설명 https://www.acmicpc.net/problem/17837 문제의 자세한 설명은 위 링크에 자세하게 나와있으니 각설하고, 핵심을 요약하자면 1. N * N 체스판이 존재 2. 각 체스판의 엔트리에는 흰색 / 빨간색 / 파란색으로 표시 3. 체스판 위에 말들을 올림(숫자) 4. 각 말들은 이동방향이 정해져있고, 각 턴마다 해당 방향으로 한칸씩 이동 5. 각 말들은 이미 다른 말이 점유하고 있는 칸으로도 이동할 수 있는데, 5-1. 말 A가 말 B가 있는 위치로 이동하면 위에 올라탈 수 있음. 즉 A | B 에서 | A/B 로 올라타게 됨 5-2. 이미 말 여러개가 겹쳐져 있는 칸에서 말이 이동시, 위에 태우고 있는 말들을 같이 이동시킴. 즉 A/B | C 에서 B가 C쪽으로 이동하면.. 2020. 3. 5.