백준
-
백준(BOJ) 17088번 등차수열 변환알고리즘 풀이/백준(Boj) 2020. 1. 12. 13:47
문제 : https://www.acmicpc.net/problem/17088 17088번: 등차수열 변환 크기가 N인 수열 A = [A1, A2, ..., AN]이 있을 때, 모든 1 ≤ i < N에 대해서, Ai+1-Ai가 모두 일치하면 등차수열이라고 한다. 예를 들어, [3], [6, 6, 6], [2, 8, 14, 20], [6, 4, 2]는 등차수열이고, [4, 5, 4], [6, 3, 1]은 등차수열이 아니다. 수열 B = [B1, B2, ..., BN]을 등차수열로 변환하려고 한다. 각각의 수에는 연산을 최대 한 번 적용할 수 있다. 연산은 두 가 www.acmicpc.net 풀이 : 모든 경우를 다해 보기에는 N이 10만이기 때문에 3^10만으로 도저히 불가능하다. 따라서 등차수열의 성질을 ..
-
백준(BOJ) 16964번 DFS 스페셜알고리즘 풀이/백준(Boj) 2020. 1. 11. 13:49
문제 : https://www.acmicpc.net/problem/16964 16964번: DFS 스페셜 저지 첫째 줄에 정점의 수 N(2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에는 트리의 간선 정보가 주어진다. 마지막 줄에는 DFS 방문 순서가 주어진다. DFS 방문 순서는 항상 N개의 정수로 이루어져 있으며, 1부터 N까지 자연수가 한 번씩 등장한다. www.acmicpc.net 풀이 : order배열을 통해 각 정점에 순서를 구해준다. 각각의 a안에 배열들을 order 순서에 맞게 정렬한다. 이후 바뀐 a로 dfs 방문을 실제로 해보고 picked배열에 저장한다. picked와 cand가 같지 않으면 0을 같다면 1을 출력한다. ex) 두번째 예제에서는 a[0]은 1 2 ..
-
백준(BOJ) 16954번 움직이는 미로 탈출알고리즘 풀이/백준(Boj) 2020. 1. 7. 14:33
문제 : https://www.acmicpc.net/problem/16954 16954번: 움직이는 미로 탈출 욱제는 학교 숙제로 크기가 8×8인 체스판에서 탈출하는 게임을 만들었다. 체스판의 모든 칸은 빈 칸 또는 벽 중 하나이다. 욱제의 캐릭터는 가장 왼쪽 아랫 칸에 있고, 이 캐릭터는 가장 오른쪽 윗 칸으로 이동해야 한다. 이 게임의 특징은 벽이 움직인다는 점이다. 1초마다 모든 벽이 아래에 있는 행으로 한 칸씩 내려가고, 가장 아래에 있어서 아래에 행이 없다면 벽이 사라지게 된다. 욱제의 캐릭터는 1초에 인접한 한 칸 또는 대각선 방향으로 인접한 한 칸으로 www.acmicpc.net 풀이 : 시간이 8초부터는 벽은 모두 내려간 상태고.(점)만 남은 상태가 된다. 이 상태에서는 무조건 목표지점(0..
-
백준(BOJ) 매직 스퀘어로 변경하기알고리즘 풀이/백준(Boj) 2020. 1. 1. 16:43
문제 : https://www.acmicpc.net/problem/16945 16945번: 매직 스퀘어로 변경하기 1부터 N2까지의 수가 하나씩 채워져 있는 크기가 N×N인 배열이 있고, 이 배열의 모든 행, 열, 길이가 N인 대각선의 합이 모두 같을 때, 매직 스퀘어라고 한다. 크기가 3×3인 배열 A가 주어졌을 때, 이 배열을 매직 스퀘어로 변경하려고 한다. 한 칸에 있는 수 a를 b로 변경하는 비용은 |a - b| 이다. 예를 들어, 아래와 같은 경우를 살펴보자. 5 3 4 1 5 8 6 4 2 이 배열의 수를 아래와 같이 변경하면 매직 스퀘어가 되고, 비용은 www.acmicpc.net 풀이 : 1. 가로 세로 3 3 은 편의를 위해 1차원 배열로 바꾸어 풀었다. 매직 스퀘어는 1~9가 중복되지 ..
-
백준(BOJ) 17779번 게리맨더링2알고리즘 풀이/백준(Boj) 2020. 1. 1. 16:31
문제 : https://www.acmicpc.net/problem/17779 17779번: 게리맨더링 2 재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름도 재현시로 변경했다. 이번 선거에서는 최대한 공평하게 선거구를 획정하려고 한다. 재현시는 크기가 N×N인 격자로 나타낼 수 있다. 격자의 각 칸은 구역을 의미하고, r행 c열에 있는 구역은 (r, c)로 나타낼 수 있다. 구역을 다섯 개의 선거구로 나눠야 하고, 각 구역은 다 www.acmicpc.net 풀이 : 1. - 우선 주어진 y, x와 d1, d2를 모르기 때문에 하나하나 다 해보아야 한다. 4중 for문을 이용..
-
백준(BOJ) 16956번 늑대와 양알고리즘 풀이/백준(Boj) 2019. 12. 29. 02:39
문제 : https://www.acmicpc.net/problem/16956 16956번: 늑대와 양 크기가 R×C인 목장이 있고, 목장은 1×1 크기의 칸으로 나누어져 있다. 각각의 칸에는 비어있거나, 양 또는 늑대가 있다. 양은 이동하지 않고 위치를 지키고 있고, 늑대는 인접한 칸을 자유롭게 이동할 수 있다. 두 칸이 인접하다는 것은 두 칸이 변을 공유하는 경우이다. 목장에 울타리를 설치해 늑대가 양이 있는 칸으로 갈 수 없게 하려고 한다. 늑대는 울타리가 있는 칸으로는 이동할 수 없다. 울타리를 설치해보자. www.acmicpc.net 풀이 : 1. S의 상하좌우의 W가 있다면 울타리를 만들 수 없으니 0을 출력할 수밖에 없다. 2. S의 상하좌우의 W인 곳이 없다면 모두 울타리를 만들 수 있으니 ..
-
백준(BOJ) 16959번 체스판 여행 1알고리즘 풀이/백준(Boj) 2019. 12. 26. 02:30
문제 : https://www.acmicpc.net/problem/16959 16959번: 체스판 여행 1 크기가 N×N인 체스판이 있고, 체스판의 각 칸에는 1부터 N2까지의 정수가 한 번씩 적혀있다. 지학이는 이 체스판을 이용해서 재미있는 게임을 해보려고 한다. 지학이가 가지고 있는 말은 나이트, 비숍, 룩이다. 가장 먼저 1이 적혀있는 칸에 말 하나를 놓는다. 그 다음, 1, 2, ..., N2 순서로 이동시키려고 한다. 먼저, 1에 나이트, 비숍, 룩 중 하나를 놓는다. 그 다음, 말을 이동시켜서 2가 적힌 칸으로 이동시킨다. 1에서 2로 이동시킬 때, www.acmicpc.net 풀이 : 중복을 저장하는 d배열을 애초에 4차원 배열로 만들어서 처리하자. d [y][x][n*n까지의 수-1][0 ..
-
백준(BOJ) 17822번 원판 돌리기알고리즘 풀이/백준(Boj) 2019. 12. 23. 02:06
문제 : https://www.acmicpc.net/problem/17822 17822번: 원판 돌리기 반지름이 1, 2, ..., N인 원판이 크기가 작아지는 순으로 바닥에 놓여있고, 원판의 중심은 모두 같다. 원판의 반지름이 i이면, 그 원판을 i번째 원판이라고 한다. 각각의 원판에는 M개의 정수가 적혀있고, i번째 원판에 적힌 j번째 수의 위치는 (i, j)로 표현한다. 수의 위치는 다음을 만족한다. (i, 1)은 (i, 2), (i, M)과 인접하다. (i, M)은 (i, M-1), (i, 1)과 인접하다. (i, j)는 (i, j-1), (i, j www.acmicpc.net 풀이 : 문제에 주어진 대로 차근차근 푸는 시뮬레이션 문제였다. 주의할 점은 flag를 통해서 인접한 곳을 발견했는지 여..