🔗 문제 링크 20303번: 할로윈의 양아치 첫째 줄에 정수 $N$, $M$, $K$가 주어진다. $N$은 거리에 있는 아이들의 수, $M$은 아이들의 친구 관계 수, $K$는 울음소리가 공명하기 위한 최소 아이의 수이다. ($1 \leq N \leq 30\ 000$, $0 \leq M \leq 100\ 000$, www.acmicpc.net 💡 문제 풀이 및 해석 첫 번째로 친구들의 집합을 만드는 것이 중요했다. 친구관계도를 만들기 위해서 myFriend를 이용해서 i번의 친구를 vector로 저장한다. 그럼 i번의 친구들의 친구들을 다시 모두 탐색한다. 단, 아직 친구 그룹이 형성되어 있다면 찾지 않는다. (이미 같은 그룹이기 때문) 1N 번의 아이를 23번 과정을 반복해서 모든 그룹을 만들어준다. ..
baekjoon
🔗 문제 링크 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 💡 문제 풀이 및 해석 경우의 수가 크지 않으므로 BruteForce로 풀 수 있을 것이라 생각했다. 일단, 0개를 설치한 경우는 반드시 조건에 성립하므로 예외처리해 준다. (안 해줘도 상관없다.) DFS 방식으로 사다리를 설치하면 브루트 포스하게 풀 수 있다. (이게 최선인지는 아직 모르겠다.) 설치할 다리의 개수를 모두 설치했을 때, 이 방식이 정답인지 확인하고 아니면 다음 경우의 수로 넘어간다. 정답이 나올 때까지 3번-4번을 반복한다. 모두..
🔗 문제 링크 1082번: 방 번호 첫째 줄에 N이 주아진다. 둘째 줄에는 공백으로 구분된 P0, ..., PN-1이 주어진다. 마지막 줄에는 M이 주어진다. www.acmicpc.net 💡 문제 풀이 및 해석 만약 0 만 살 수 있거나 N == 1인 경우 방번호는 0으로 고정이다. 가장 큰 수는 어떤 수일까? 2-1. 자릿수가 긴 수이다. 2-2. 자릿수가 같다면, 앞에서부터 비교할 때, 앞자리의 수가 큰 수이다. 먼저 0을 제외한 가장 코스트가 낮은 숫자를 찾아 맨 앞자리에 넣는다. 0과 비교해서 더 낮은 코스트인 수를 뒤에 최대한 많이 붙인다. 가장 앞자리부터 9 ~ 앞자리의수 까지 비교해서 교체할 수 있으면 교체한다. ⭐️ 정답 코드 및 설명 #include #include using namesp..
🔗 문제 링크 1069번: 집으로 은진이는 지금 (X, Y)에 있고, (0, 0)에 있는 집으로 가능한 빨리 가려고 한다. 이동할 수 있는 방법은 다음 두 가지이다. 첫 번째 방법은 걷는것이다. 걸을 때는 1초에 1만큼 움직인다. 두 번째 방법 www.acmicpc.net 💡 문제 풀이 및 해석 점프와 걷기가 있다. 만약, 점프가 걷기보다 느리다면, 굳이 점프할 필요없이 걷기로만 이동하면 된다. 충분히 가까워 진 순간은 "점프 2번으로 갈 수 있는 거리" > "현재 위치에서 목적지까지의 거리" 이다. 2번 지점에서는 2가지 선택지가 있다. 3-1. 조금 돌아서 가는 점프 2번의 거리 (최단 경로가 아닌, ^ 모양으로 위로 조금이동하고 아래로 이동하는 방법) 3-2. 목적지를 점프 경로안에 넣고, 남은 거..
🔗 문제 링크 2631번: 줄세우기 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 www.acmicpc.net 💡 문제 풀이 및 해석 최소한의 인원을 이동시키면서 줄을 세워야 하는 문제이다. 줄을 세운다 => 숫자를 정렬한다 => 정렬할 때, 최대한 적게 움직여야 한다. 움직이는 인원 = 전체 - 움직이지 않아도 되는 인원 움직이지 않아도 되는 인원 = 이미 줄이 제대로 돼있는 인원 따라서 이미 정렬이 되어있는 인원을 전체에서 빼주면 된다!! 내 위치에서 내 앞에 있는 인원들을 비교하여 나까지 증가하는 부분 수열을 구하면 된다. ⭐️ 정답 코드 및 설명 impor..
🔗 문제 링크 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..
