🔗 문제 링크 2631번: 줄세우기 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 www.acmicpc.net 💡 문제 풀이 및 해석 최소한의 인원을 이동시키면서 줄을 세워야 하는 문제이다. 줄을 세운다 => 숫자를 정렬한다 => 정렬할 때, 최대한 적게 움직여야 한다. 움직이는 인원 = 전체 - 움직이지 않아도 되는 인원 움직이지 않아도 되는 인원 = 이미 줄이 제대로 돼있는 인원 따라서 이미 정렬이 되어있는 인원을 전체에서 빼주면 된다!! 내 위치에서 내 앞에 있는 인원들을 비교하여 나까지 증가하는 부분 수열을 구하면 된다. ⭐️ 정답 코드 및 설명 impor..
baekjoon
🔗 문제 링크 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 💡 문제 풀이 및 해석 평범한 BFS 문제로 본다면, 모든 지점에서 BFS 알고리즘을 구현하여 실행하면 된다. 적록색약과 아닌 상황을 구분해야 하므로, 아래와 같은 과정을 거쳐야 한다. 3-1. 적록색맹이 아닌 사람에 대해서 BFS로 검사한다. 3-2. 적록색맹인 사람은 R -> G 로 바꿔서 검사한다. ⭐️ 정답 코드 및 설명 import javax.naming.PartialResultException; import java.awt.imag..
🔗 문제 링크 2194번: 유닛 이동시키기 첫째 줄에 다섯 개의 정수 N, M(1 ≤ N, M ≤ 500), A, B(1 ≤ A, B ≤ 10), K(0 ≤ K ≤ 100,000)가 주어진다. 다음 K개의 줄에는 장애물이 설치된 위치(행 번호, 열 번호)가 주어진다. 그 다음 줄에는 시작점의 www.acmicpc.net 💡 문제 풀이 및 해석 "시작점 -> 도착점"의 최소거리를 구해야 한다는 점에서 BFS로 풀어야 한다 생각했다. 단, queue에 들어간 모든 원소가 빠져나가는 것을 1회로 지정해야 한다. 이 때, 움직이는 Unit은 동서남북으로 한칸씩 움직일 수 있는데, 장애물이 설치된 구역이거나 맵의 바깥쪽으로는 이동할 수 없다. 동서남북으로 이동시에 방향에 맞게 유닛이 이동하는 변이 금지구역에 들어..
🔗 문제 링크 13424번: 비밀 모임 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 방 www.acmicpc.net 💡 문제 풀이 및 해석 N의 범위가 100 이하이므로, 1N번 방에서 1N번 방까지 가는 최소값 거리를 모두 구해도 1초안에 해결되는 문제다. 모든 방에서 모든 방까지 가는 최소의 거리를 다익스트라를 통해서 구한다. 이 최솟값들을 모든 방에 더해준다. 가장 값이 작은 방이 모이기 최적화된 방이다. 값이 같은 경우, 번호가 낮은 수가 출력되어야 한다. ⭐️ 정답 코드 및 설명 #include #include #include #include #defin..
🔗 문제 링크 20058번: 마법사 상어와 파이어스톰 마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c www.acmicpc.net 💡 문제 풀이 및 해석 회전을 시켜야 하는데, 이는 2^N 이다. N북, 남->서, 동->남, 저장된 북->동 순서로 돌렸다. rotate 하는 함수는 L에 영향을 받는데, 이는 매개 변수 size로 넣어주었다. rotate는 왼쪽 위, 오른쪽 아래 2개의 x,y rotate해야 되는 정사각형의 변을 표현하였다. 그 다음은 녹이는 것과 bfs인데, 굳이 설명해놓지 않겠다. ⭐️ 정답 코드 및 설명 #include #include ..
🔗 문제 링크 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..
