문제 문제 바로가기> SWEA 4193번: 수영대회 결승전 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 우승 경로 (= 가장 빠른 시간 내 도착점) 에 도착해야하므로, BFS를 이용했다! 소용돌이는 2초동안 유지되다가 1초동안 잠잠해지므로, 현재시간 % 3 == 2 인 경우가 소용돌이가 잠잠해지는 경우이다! 소용돌이가 잠잠해지지 않은 경우에는 현재 위치에서 대기해야하므로, 초를 + 1 한 후, 현재 정보를 다시 queue에 넣어 주었다! #include #include #include #define MAX 16 #define EMPTY 0 #define WALL 1 // 섬과 같은 장애물 #define..

문제 문제 바로가기> BOJ 16987번: 계란으로 계란치기 16987번: 계란으로 계란치기 원래 프로그래머의 기본 소양은 팔굽혀펴기를 단 한 개도 할 수 없는 것이라고 하지만 인범이는 3대 500을 넘기는 몇 안되는 프로그래머 중 한 명이다. 인범이는 BOJ에서 틀린 제출을 할 때마다 턱 www.acmicpc.net 풀이 브루트포스 방식으로 가능한 모든 경우를 탐색해서 "인범이가 깰 수 있는 계란의 최대 개수"를 구해주었다! import java.io.*; import java.util.*; public class Main { static int N, ans; static int[][] egg; public static void main(String[] args) throws Exception { Bu..

문제 문제 바로가기> BOJ 6987번: 월드컵 6987번: 월드컵 월드컵 조별 최종 예선에서는 6개국으로 구성된 각 조별로 동일한 조에 소속된 국가들과 한 번씩, 각 국가별로 총 5번의 경기를 치른다. 조별리그가 끝난 후, 기자가 보내온 각 나라의 승, 무승부 www.acmicpc.net 풀이 경기가 진행될 수 있는 모든 경우의 수를 탐색하여, 그 중 하나라도 결과 값과 일치하는 게 있다면 (= 가능한 결과), 1을 출력하도록 풀었다. 모든 경우의 수를 탐색할 경우, 시간 복잡도는 3^15(=14,348,907)(*4 = 57,395,628)로 시간 내 완전탐색이 가능하다! 총 경기 경우의 수는 6C2 = 15 이고, (이 조합을 미리 만들어주는 부분이 make_team() 함수) 두 팀이 경기를 진행..

문제 문제 바로가기> BOJ 12100번: 2048 (Easy) 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 풀이 블록이 이동하는 순서를 미리 정해 놓은 뒤 시뮬레이션 해보는 문제다. 블록을 합칠 때, vector를 이용하면 좀 더 쉽게 문제를 해결할 수 있다. C++ #include #include #define MAX 21 #define CNT 5 using namespace std; int N, ans=0; int dir[CNT]; vector tmp; int map[MAX..

문제 문제 바로가기> BOJ 17472번: 다리 만들기 2 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 풀이 1. 섬 (2 ≤ 섬의 개수 ≤ 6) 에 대표 번호? 를 매겨주었다. 어떤 섬에서 어떤 섬으로 이어지는 다리인지 알기 위해서! 2. 문제에서 준 조건인, ▷ 다리의 길이 > 2 ▷ 중간에 방향 변화 불가 를 만족 시키는 다리(edge)가 이어주는 섬 두개 (from, to), 다리 길이(len)를 pq에 넣어준다! 이 때, 상 하 좌 우 탐색을 모두 진행하면, 중복되는 edge들..

문제 문제 바로가기> BOJ 17779번: 게리맨더링 2 17779번: 게리맨더링 2 재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름 www.acmicpc.net 풀이 얼핏 보면 조건이 굉장히 까다로워 보이지만,, 사실 문제에서 경계의 범위를 다 주고 있기 때문에,, 그대로 조건식만 넣어주면 된다! 사실 개꿀인 ㅎ 나름 중요한 포인트? 가 있다면, 5번 구역의 경계를 먼저 설정해 두고, 그 경계만 침범?하지 않도록 해주면 된다! 이 후 `모든 인구 수 - 1,2,3,4 지역 인구` 를 해주면 5번 구역 인구도 쉽게 구할 수 있다!! 아무래도 그림으로 보면 이해가 더 쉬울 ..

문제 문제 바로가기> BOJ 17142번: 연구소 3 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 풀이 1. 조합을 구현하여, 바이러스 M개를 활성 상태로 변경 2. BFS를 이용하여 바이러스가 모두 퍼지는 시간을 구하고, ans 값 갱신 * 비활성 바이러스 → 활성화 될 때는 바이러스가 퍼지는 시간으로 계산 x ( = 값 update x ) * 빈 칸에 바이러스가 퍼지는 것은 바이러스를 퍼뜨리는 데 걸린 시간에 영향을 주지만, 비활성화된 바이러스가 있는 곳으로 바이러스가 퍼지는 것은 바이러스를 퍼뜨리는 데 걸린 시..

문제 문제 바로가기> BOJ 17135번: 캐슬 디펜스 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net 풀이 1. 조합을 구현하여 궁수의 위치를 선정한다. (`solution() 함수`) 2. 정해진 궁수의 위치를 기반으로, 다음을 과정을 반복한다. 궁수의 적 공격 - 공격할 적의 우선순위를 구하기 위해 , pq에서 사용할 ATTACK 구조체 내에서 bool operator를 재정의해주었다. - 모든 궁수는 동시에 공격하므로, 공격 위치를 vector에 넣어두었다가 한 번에 공격해주었다. (이때, 이미 제거한 적을 또 c..

문제 문제 바로가기> BOJ 15683번: 감시 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 풀이 cctv의 개수가 최대 8개로 적은 편이다. 따라서 가능한 cctv 방향을 모두 시뮬레이션 해보면서, 브루트포스 방식으로 문제를 풀었다. 탐색 방향을 미리 `dir` 배열에 정해두고, 모든 cctv의 방향을 정했을 때, 시뮬레이션 해주면 된다. C++ #include #include #define EMPTY 0 #define WALL 6 #define MAX 10 using namespace std;..

문제 문제 바로가기> BOJ 17406번: 배열 돌리기 4 17406번: 배열 돌리기 4 크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의 www.acmicpc.net 풀이 우선 K가 최대 6으로 작기 때문에, 모든 경우의 수를 탐색하는 방법으로 문제를 풀 수 있다. 문제를 풀 때 필요한 점은 다음 2가지 였던 것 같다. 1. 순열을 구현할 수 있는가? 2. 배열을 원하는 대로 조작할 수 있는가? 1(순열 구현) 을 만족하기 위해, cnt 변수와 visited 배열을 활용하여 재귀적으로 호출을 해주었다. 2(배열 조작)은 규칙을 찾는 게 중..

문제 문제 바로가기> BOJ 14502번: 연구소 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 풀이 벽 3개를 놓을 수 있는 모든 조합의 경우를 고려해서, 안전 영역의 최대 크기를 구해 주면 된다! C++ #include #include #define MAX 9 #define EMPTY 0 #define WALL 1 #define VIRUS 2 using namespace std; int N, M; int ans = 0; int lab[MAX][MAX]; int copy_lab[MAX][MAX]; int dy[] = {..

문제 문제 바로가기> BOJ 14889번: 스타트와 링크 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 풀이 start와 link 팀을 나눌 수 있는 모든 경우의 수로 나누어주고, 두 팀의 능력치 차이의 최솟값을 구해주었다. C++ #include #include #define MAX 21 #define INF 1000000001 using namespace std; int N, ans = INF; int score[MAX][MAX]; bool start_team[MAX]; void input() { cin >> N; for (i..

문제 문제 바로가기> BOJ 15686번: 치킨 배달 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 풀이 조합을 통해 M개의 치킨집을 선택하고, 집들과의 맨해튼 거리를 구해서, 도시의 치킨 거리의 최솟값을 구해줄 수 있다! C++ #include #include #define MAX 14 #define INF 1000000001 #define EMPTY 0 #define HOUSE 1 #define CHICKEN 2 using namespace std; int selected[MAX]; ..

문제 문제 바로가기> BOJ 14888번: 연산자 끼워넣기 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 풀이 모든 경우의 수를 탐색하며, 최댓값과 최솟값을 구해주면 된다! C++ #include #define MAX 12 using namespace std; int N; int max_val = -100000001; // 만들 수 있는 식의 결과의 최댓값 int min_val = 100000001; // 최솟값 int A[MAX], oper[4]; //..