🔗 문제 링크 20058번: 마법사 상어와 파이어스톰 마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c www.acmicpc.net 💡 문제 풀이 및 해석 회전을 시켜야 하는데, 이는 2^N 이다. N북, 남->서, 동->남, 저장된 북->동 순서로 돌렸다. rotate 하는 함수는 L에 영향을 받는데, 이는 매개 변수 size로 넣어주었다. rotate는 왼쪽 위, 오른쪽 아래 2개의 x,y rotate해야 되는 정사각형의 변을 표현하였다. 그 다음은 녹이는 것과 bfs인데, 굳이 설명해놓지 않겠다. ⭐️ 정답 코드 및 설명 #include #include ..
baekjoon
🔗 문제 링크 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 💡 문제 풀이 및 해석 문제의 조건대로 풀면된다. 단, 사전 작업으로 해야할 일이 있다. 이 나라는 이번 회차(인구 이동 당일)에 인구 이동이 일어났는가 국경선이 열린 이웃한 나라들의 집합은 어떻게 처리할 것인가 인구가 이동하지 않은 것은 어떻게 알 것인가 더 자세한 풀이는 코드의 주석에 있으니 코드의 흐름대로 읽으면 이해할 수 있을 것이다. ⭐️ 정답 코드 및 설명 #include #include #include #define end..
🔗 문제 링크 https://www.acmicpc.net/problem/5052 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net 💡 문제 접근 가장 먼저 접두사를 어떤 순서로 검사할지 정해야 하는데, 여기서 문제는 이 기준을 어떻게 정할 것인지다. 일단, 최소한 길이가 긴 전화번호가 짧은 전화번호의 접두사가 될 일은 없는데, 이런 방식으로 풀면 뒤의 모든 전화번호들을 검사해야 되기 때문에, 시간초과가 났다. 여기서 정렬을 하면서 힌트를 얻은 것이 있는데, string을 정렬하면 [123..
🔗 문제 링크 https://www.acmicpc.net/problem/14890 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 💡 문제 풀이 및 해석 한칸씩 이동하는 문제이다. 이동하는 케이스는 총 3가지이다. Case 1 : 평지 이동, Case 2 : 위로 이동, Case 3 : 아래로 이동 Case 1 : 연속해서 평지를 이동할 때마다 연속으로 이동한 칸 수(Stack)를 더해준다. Case 2 : 위로 이동하는 것은 (연속으로 이동한 칸 수 >= L) 이어야 가능하다. 위로 이동한 칸은 경사로를 설치할 수 있으므로 Stac..
🔗 문제 링크 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 💡 문제 풀이 및 해석 탑은 왼쪽에서 오른쪽으로 만들고, 탐색은 오른쪽에서 왼쪽으로 진행된다. 자신보다 크거나 같은 탑을 만나면 더 이상 신호가 왼쪽으로 가지 않는다. 1번과 2번을 종합하면, 오른쪽 탑부터 왼쪽 탑으로 탐색을 해야 하는데, 현재 탑을 기준으로 오른쪽에 있는 탑들의 집합에서 가장 작은 탑보다 작다면, 현재 탑도 집합에 넣어주고, 아니라면 현재 탑의 높이보다 작거나 같은 탑들은 현재 탑에 수신된다고 표시해주면 된다. 종합적으로 in..
🔗 문제 링크 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net 💡 문제 풀이 및 해석 봄 -> 여름 -> 가을 -> 겨울 순으로 구현하면 된다. 다른 점은 없다. 상도의 땅 정보를 받을 수 있는 구조를 struct를 통해 만들어준다. 봄에 양분을 못먹은 나무는 여름에 죽고 양분이 된다. -> 봄과 여름을 연관성있게 코드를 짜면 시간을 단축할 수 있다. 번식할 수 있는 나무는 5의 배수다. -> 5의 배수인 나무만 따로 체크해두면, 모든 나무를 검사할 필요가 없다. (번식한 나무가 죽는 것도 아니..
🔗 문제 링크 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 💡 문제 풀이 및 해석 CCTV는 최대 8개이다. 모든 경우를 생각하면, 최악의 경우 (4번 CCTV가 64개 있을 때, 실제로는 3방향이니 24보다 많이 작다.) 4^8 (모든 CCTV의 모든 방향 체크) \* 64 (맵의 복사) \* 24 (CCTV가 보는 방향 체크) = 100,663,296이다. bruteforce한 방법으로 찾을 수 있다. 나머지는 문제 조건 그대로 구현해주면 된다. ⭐️ 정답 코드 및 설명 #include #in..
🔗 문제 링크 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 💡 문제 풀이 및 해석 먼저 가로, 세로 조건이 8이하이다. 따라서 전체 칸은 64칸이다. 3개의 모든 기둥을 박아야 하므로 64개의 칸 중에서 3개를 선택하는 조합, 그리고 그 상태에서 BFS를 진행한다고 하면, 최대 $64\times63\times62\over3\times2\times1$ $\times64 = 2,666,496$ 이 된다. 이를 토대로 완전탐색을 진행하기로 하였다. 먼저 64개의 칸중 3개의 칸을 조합으로 구성한다. 그 구성이 실제로 가능하면..
