문제 문제 바로가기> BOJ 15685번: 드래곤 커브 15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커 www.acmicpc.net 풀이 드래곤 커브를 살펴보면, 규칙이 있는데, 다음 세대에 추가되는 선분의 방향 = `(이전 세대의 방향 정보를 역순 탐색 + 1) % 4` 를 한 것이 된다. 따라서 해당 규칙에 맞추어서 구현해주었다! 주의할 점은 역순으로 꺼내서 이어 붙어줘야 하는 것인데, 이 부분은 예제를 살펴보면 쉽게 이해할 수 있을 것 같다. C++ #include #include #define MAX 10..

문제 문제 바로가기> 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 14891번: 톱니바퀴 14891번: 톱니바퀴 총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴 www.acmicpc.net 풀이 문제에서 요구하는 대로 구현해주면 되는 간단한 문제였다! 1. 톱니바퀴가 맞닿은 극이 같은지, 다른지 판단하여 방향을 저장한다. 2. 저장해둔 방향대로 회전을 진행한다. 3. 점수를 계산한다. 다만,, 톱니바퀴 회전 전 방향을 저장하지 않고, 회전 후 바뀐 방향으로 비교하는 바람에 조금 헤맸다 ^^,, C++ #include #include #define MAX 4 #define SIZE 8 using ..

문제 문제 바로가기> BOJ 14890번: 경사로 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 2N 개의 길 모두를 살펴보면서 지나갈 수 있는 길의 개수를 세어주면 된다. 이때, 총 4가지 경우의 수가 있다. 1. 이전 칸과 높이가 같은 경우 ▶ 같은 높이의 칸을 세어주는 변수인 `cnt` 를 1 증가시켜준다. 2. 높이가 낮아지는 경우 (높이 차 = 1) ▶ 해당 칸을 제외하고, 앞으로 1-L개의 칸의 높이가 같아야, 경사로를 건설할 수 있다. 3. 높이가 높아지는 경우 (높이 차 = 1) ▶ 지금까지 L개 이상의 칸의 높..

문제 문제 바로가기> 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 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 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 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..

문제 문제 바로가기> 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 16236번: 아기상어 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 풀이 문제의 요구사항에 따라 구현해 주면 된다. 설명은 주석으로 자세히 적어 놓았다! 이런 문제는 물고기 먹은 처리, 상어 정보 update 등을 잊지 않고 해주는 게 중요한 것 같다. 문제를 풀 때, 알고 있으면 도움이 되는 개념은 다음과 같다! ✔️ operator 재정의 ✔️ 구조체 정의 ✔️ 그래프 탐색 C++ #include #include #include #define MAX 21 using n..