목록2022/04/28 (3)
Hey Tech
📝 문제 https://www.acmicpc.net/problem/17143 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net 💡 접근법 문제에 주어진 조건을 빠짐 없이 고려하여 구현해야 정답을 맞출 수 있습니다. 낚시왕이 컬럼(column) 방향으로 움직이므로 컬럼을 기준으로 전체 로직이 수행됩니다. 컬럼이 결정되면 로우(row) 방향으로 상어가 있는지 탐색하고, 가장 작은 로우에 있는 상어를 낚습니다. 상어의 진행방향을 고려하여 상어의 속도까지 한 칸씩 이동시키며 상어가 이동 가능한지 체크..
📝 문제 https://www.acmicpc.net/problem/19236 19236번: 청소년 상어 첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 www.acmicpc.net 백준 내 아기 상어 문제의 후속 버전입니다. 💡 접근법 사용 알고리즘: DFS 알고리즘 상어가 잡아먹은 물고기 번호의 최댓값을 구해야 합니다. 상어가 어떤 물고기부터 잡아먹었는지, 그 순서에 따라 뒤이어 잡아먹을 수 있는 물고기 조합이 달라질 수 있습니다. 따라서 2번째 물고기를 선택하여 최대한 많이 먹을 수 있을 때까지 재귀적으로 물고기와 상어를 이동시켜 보는 로직을 ..
📝 문제 https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 💡 접근법 DFS 알고리즘을 활용하여 문제를 해결하였습니다. 문제 풀이는 다음과 같이 크게 세 부분으로 나눌 수 있습니다. 첫째, DFS 알고리즘을 활용하여 CCTV 종류별, 방향 전환에 따른 새로운 감시영역을 재귀적으로 탐색하는 함수 둘째, 특정 방향을 바라보는 CCTV의 최대 감시영역을 찾는 함수 셋째, 모든 CCTV에 대해 탐색이 끝나면 사각지대의 최솟값을 구하는 함수 C..