문제 문제 바로가기> BOJ 21608번: 상어 초등학교 21608번: 상어 초등학교 상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호 www.acmicpc.net 풀이 문제를 풀 때 중요하다고 느낀 점을 몇가지 적어보겠다. 1. 자리를 정할 때 우선순위 별로 정렬하기 위해 priority_queue를 이용 * 이때, 구조체 내 연산자 재정의 방법을 알고 있어야 한다. (좋아하는 학생 수 > 빈칸 > 작은 행 번호 > 작은 열 번호) 우선으로 연산자 재정의를 해주어야 하기 때문! 2. 이미 자리가 정해진 경우 continue 해주기 이미 자리가 정해졌는데, ..
문제 문제 바로가기> BOJ 23290번: 마법사 상어와 복제 23290번: 마법사 상어와 복제 첫째 줄에 물고기의 수 M, 상어가 마법을 연습한 횟수 S가 주어진다. 둘째 줄부터 M개의 줄에는 물고기의 정보 fx, fy, d가 주어진다. (fx, fy)는 물고기의 위치를 의미하고, d는 방향을 의미한다. 방향 www.acmicpc.net 풀이 문제를 풀 때 중요하다고 느낀 점을 몇가지 적어보겠다. 1. 배열 index 0 부터 시작할거면, 입력 시 위치, 방향 -1 해주기!! 2. 이동 못한 물고기는 제자리에 넣어주기 !! (`ismove` 변수를 이용해 찾지 못한 경우 제자리에 기존 방향으로 넣어주었다.) 안 그러면 물고기가 중간에 사라져 버리는 현상 발생 ^^ 3. 상어의 움직임 시뮬레이션할 때, ..
문제 문제 바로가기 > BOJ 17143번: 낚시왕 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net 풀이 문제를 풀 때 중요하다고 느낀 점을 몇가지 적어보겠다. 1. 상어 이동 시 편의를 위해, num 배열을 만들고, 해당 상어의 정보(순서)를 저장해 둔다. num[r][c] = i : (r, c) 위치의 상어는 i번째 상어 ( = shark[i]의 위치는 (r, c)) 2. 시간 초과 방지를 위해 상하 이동인 경우에는, s%=(2*R-2) 좌우 이동인 경우에는, s%=(2*C-2) 을 적용..
문제 문제 바로가기> BOJ 15663번: N과 M (9) 15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 풀이 같은 위치에 같은 수가 오게되면, 중복 수열이 되므로, 이를 방지하기 위해 `prev` 를 이용해서 같은 자리에 같은 수가 오지 못하도록 해주었다! #include #include #define MAX 10 using namespace std; int N, M; bool isused[MAX]; int num[MAX], ans[MAX]; void input() { cin >> N >> M; for (..
문제 문제 바로가기> BOJ 17144번: 미세먼지 안녕! 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 풀이 문제에서 요구하는 대로 구현만 해주면 된다! C++ #include #define MAX 51 using namespace std; int ar = 0; int R, C, T; int home[MAX][MAX]; int copy_home[MAX][MAX]; int dr[] = {-1, 1, 0, 0}; int dc[] = {0, 0, -1, 1}; void input(){ cin >> R >> C ..
문제 문제 바로가기> 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]; //..
문제 문제 바로가기> BOJ 14503번: 로봇 청소기 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 풀이 문제에서 설명한 조건에 따라 구현해주면 된다! 문제의 2-1, 2-2 조건은 현재 위치에서 반 시계 방향으로 돌면서 청소 가능한 위치를 찾는 것을 의미한다! [북 동 남 서] 순서의 배열이기 때문에, 반시계 방향은 -1을 해주면 된다. 이때, "북(0)-1 = -1" 이므로, 이를 방지하기 위해 "(d-1+4)%4 = (d+3)%4" 를 해준 것이다. C++ #include #include #defin..
문제 문제 바로가기> SWEA 3234번: 준환이의 양팔저울 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 " 오른쪽 추의 무게
문제 문제 바로가기> BOJ 2573번: 빙산 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 풀이 dfs를 사용하여 빙하가 분리되었는지 확인해주는 방식으로 문제를 풀었다! #include #include #define MAX 301 using namespace std; int N, M; bool allmelt; int arr[MAX][MAX]; int copy_arr[MAX][MAX]; bool visited[MAX][MAX]; int dy[] = {-1, 1, 0, 0}; int dx[] = {0, ..
문제 문제 바로가기> BOJ 11057번: 오르막 수 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 풀이 아래와 같은 규칙을 가지므로, 점화식이 dp[i][j] = (dp[i][j-1] + dp[i-1][j])%DIV 이다! #include #define MAX 1001 #define DIV 10007 using namespace std; int N; int dp[MAX][11]; int main(){ ios_base::sync_with_stdio(0); cin.tie(0)..
문제 문제 바로가기> BOJ 5014번: 스타트링크 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 풀이 BFS를 사용해서 푸는 문제였다! #include #include #define MAX 1000001 using namespace std; int F, S, G, U, D; bool visited[MAX]; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin >> F >> S >> G >> U >> D; visited[S] = true; queue q; q.push(..
문제 문제 바로가기> BOJ 16236번: 아기상어 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 풀이 문제의 요구사항에 따라 구현해 주면 된다. 설명은 주석으로 자세히 적어 놓았다! 이런 문제는 물고기 먹은 처리, 상어 정보 update 등을 잊지 않고 해주는 게 중요한 것 같다. 문제를 풀 때, 알고 있으면 도움이 되는 개념은 다음과 같다! ✔️ operator 재정의 ✔️ 구조체 정의 ✔️ 그래프 탐색 C++ #include #include #include #define MAX 21 using n..