BOJ
-
백준(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를 통해서 인접한 곳을 발견했는지 여..
-
백준(BOJ) 17143번 낚시왕알고리즘 풀이/백준(Boj) 2019. 12. 19. 14:43
문제 : https://www.acmicpc.net/problem/17143 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. 칸에는 상어가 최대 한 마리 들어있을 수 있다. 상어는 크기와 속도를 가지고 있다. 낚시왕은 처음에 1번 열의 한 칸 왼쪽에 있다. 다음은 1초 동안 일어나는 일이며, 아래 적힌 순서대로 일어난다. 낚시왕은 가장 오른쪽 열의 오른쪽 칸에 이동하 www.acmicpc.net 풀이 : 속도 배열, 크기 배 열등을 tuple로 한꺼번에 모아서 처리해보았다. 를 나타낸다. 옮길 때에는 옮긴 상어들끼리의 ..
-
백준(BOJ) 16918번 봄버맨알고리즘 풀이/백준(Boj) 2019. 12. 19. 14:37
문제 : https://www.acmicpc.net/problem/16918 16918번: 봄버맨 첫째 줄에 R, C, N (1 ≤ R, C, N ≤ 200)이 주어진다. 둘째 줄부터 R개의 줄에 격자판의 초기 상태가 주어진다. 빈 칸은 '.'로, 폭탄은 'O'로 주어진다. www.acmicpc.net 풀이 : v벡터 배열에는 폭탄 여부 , 폭탄 시간을 넣어서 풀이하였다. 폭탄 설치는 짝수 시간에만 해주어야 하고 터뜨릴 때에는 기존 터뜨릴 좌표를 0으로 만들 수 있기 때문에 temp라는 복사된 배열을 이용하였다. 코드( C++ )
-
백준 BOJ 13458번 시험 감독알고리즘 풀이/백준(Boj) 2019. 12. 17. 14:20
문제 : https://www.acmicpc.net/problem/13458 13458번: 시험 감독 첫째 줄에 시험장의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 각 시험장에 있는 응시자의 수 Ai (1 ≤ Ai ≤ 1,000,000)가 주어진다. 셋째 줄에는 B와 C가 주어진다. (1 ≤ B, C ≤ 1,000,000) www.acmicpc.net 풀이 : 총 감독관 1명은 무조건 있어야 하므로 sum++ 를 해주자. 총감독관이 커버하고 남은 수가 0보다 크다면 부감독관을 써야 한다. 부감독관이 커버할 수 보다 남은 수가 적다면 1명만 쓰면 되므로 단순히 +1을 아니라면 나눈 수만큼 더해주자. 이때 나누어 떨어지지 않는다면 +1을 추가로 해주어야 한다. ( sum을 long ..
-
백준(BOJ) 12100번 2048 (Easy)알고리즘 풀이/백준(Boj) 2019. 12. 15. 15:55
문제 : https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴이다. 블록은 적어도 하나 주어진다. www.acmicpc.net 풀이 : solve 함수는 각 함수마다 위쪽 아래쪽 왼쪽 오른쪽으로 배열 a를 몰아준 후에 cnt가 5가 될 때까지 재귀 함수를 돌린다. 5번 다 몰았다면 이때 가장 큰값은 2중 for문을 통해 best에 저장한다. 코드 ( C++ )