🔗 문제 링크https://www.acmicpc.net/problem/17142💡 문제 풀이 및 해석간단하다. 모든 칸은 감염시켜야 한다.정해진 갯수를 골라서 모든 칸을 감염시키는데 걸리는 시간이 최소가 되게 해야한다. 단, 감염시킬 수 없는 칸이 존재한다면 -1을 반환한다.애먹은 점이 이 조건이다. 바이러스를 활성화 시켰을 때, 비활성 바이러스도 있는 것으로 간주한다. 이는 비활성 바이러스가 있는 칸을 감염시키며 나아갈 수는 있지만, 감염시키지 않아도 그 칸은 감염되어 있는 것으로 간주한다는 뜻이다. 이를 설명하는 설명 예시이다.⭐️ 정답 코드 및 설명#include#include#include#include#define INF 987654321using namespace std;int N, M, ..
전체 글
🔗 문제 링크https://www.acmicpc.net/problem/17140💡 문제 풀이 및 해석33배열이 주어지고, 최대로 늘어날 수 있는 크기는 100이다. 따라서 미리 100100 크기의 배열로 만들어준다. 단, r,c가 1이상이므로 인덱스도 1~100까지 즉 101칸을 만든다.R과 C연산을 만들어야 하는데, 간단하다. 칸이 100개 이하이므로 상식적으로 숫자가 1이 100개가 들어가도 100이니 배열의 크기도 100으로 고정해두면 된다. 단, 인덱스는 숫자를 판단해야 하므로 1~100으로 정한다.이제 연산에서 각 번호를 인덱스에 카운팅하고, pair 로 vector에 넣어준다. 이 다음에 조건에 맞게 compare 함수를 만들고, 조건에 맞게 정렬해준다.R과 C 연산을 100번 이하로 돌린..
🔗 문제 링크https://www.acmicpc.net/problem/16236💡 문제 풀이 및 해석아기 상어는 매초 상하좌우로 1칸을 이동할 수 있다. 단, 자신보다 큰 물고기가 있는 칸은 갈 수 없다.아기 상어는 자신보다 작은 물고기를 잡아먹을 수 있다.아기 상어는 가장 가까운 물고기를 잡아먹으러 간다. 단, 거리가 같다면 가장 위쪽 그리고 가장 왼쪽에 있는 물고기를 잡아먹으러 간다.잡아먹으러 갈 수 있는 물고기가 없다면, 엄마를 부른다.(끝난다)위 조건들을 순서대로 BFS방식으로 코드를 짜면 된다. 3번의 조건은 가장 가까운 물고기가 2마리 이상이라면 모든 물고기 중 가장 위쪽에 있고 가장 왼쪽에 있는 물고기를 판별하여 먹으러가게하면 된다.⭐️ 정답 코드 및 설명#include#include#i..
🔗 문제 링크https://www.acmicpc.net/problem/1083💡 문제 풀이 및 해석배열의 크기가 최대 50이므로 항상 최대로 옮긴다고 해도 50 * 49 / 2 밖에 되지 않는다. 완전탐색, 그리디 방식으로 풀 수 있다는 뜻이다.문제 풀이 순서도는 다음과 같다.2-1. 기회가 끝나거나(S == 0) 모두 정렬(left == right)이 될때까지 반복한다.2-2. 옮길 수 있는 기회만큼(left_index + S) 탐색한다. 단, 탐색이 N을 넘어가는 순간 멈춘다.2-3. 탐색한 범위에서 가장 큰 숫자의 위치와 left_index의 위치를 교환한다. 그만큼 기회를 차감한다.2-4. 교환을 한 뒤에는 다음으로 정렬하는 위치를 옮겨준다. (left_index + 1)⭐️ 정답 코드 및 설..
🔗 문제 링크https://www.acmicpc.net/problem/1197💡 문제 풀이 및 해석문제에서 최소 스패닝 트리라고 나와 있으므로 같은 방식으로 풀면 좋다.사실 최소 스패닝 트리가 기억이 잘 나지 않지만, 일단 트리 형식을 갖추면서 가중치가 가장 적은 트리를 만들어야 한다는 것을 알 수 있다.그러면 최대한 낮은 비용의 간선부터 연결해야 한다.단, 간선을 연결할 때, Cycle이 생기면 안된다. => Root가 같은 것들끼리는 연결해서는 안된다.따라서 비용을 오름차순으로 정렬하고 4번을 지키면서 낮은 것들을 계속 연결해가면 된다.단, 매번 부모를 계속 찾을 수 없으므로 매번 현재 나의 Root가 무엇인지 업데이트 해준다.⭐️ 정답 코드 및 설명#include #include #include..
🔗 문제 링크https://www.acmicpc.net/problem/1253💡 문제 풀이 및 해석일단 수가 10억까지 늘어날 수 있다. 이는 배열을 만들어서 풀면 메모리초과가 발생하니 배열로 풀 수 없는 문제이다.그러면 모든 수에 대해서 모든 경우를 더해야하나? 이것도 아니다. 2000개가 있을 때, 2000 * 2000 * 1999 / 2 라는 식을 계산해보면 40억이라는 숫자가 나온다. 따라서 모든 경우를 구하는 방법도 안된다.이런 문제를 풀어본 경험이 있다면 비교적 쉽게 풀이 방식을 찾을 수 있다. 바로 투 포인터이다.3-1. 배열을 입력받은 뒤 정렬한다.3-2. 가장왼쪽의 숫자와 가장 오른쪽의 숫자를 정한다.3-3. 둘의 합이 내가 구할려는 숫자보다 작으면 left++ 크다면 right--를..
🔗 문제 링크https://www.acmicpc.net/problem/1106💡 문제 풀이 및 해석냅색 문제지만, 주의해야 할 점이 한가지 있다. 적어도 C명 늘이기 위해 형택이가 투자해야 하는 돈의 최솟값을 구해야 하는 것이다. 이는 C명을 늘리거나 혹은 그 이상 늘렸을 때, 최소비용이 되어야 한다는 뜻이다. 따라서 C명보다 많이 뽑아도 C명을 뽑을 때의 최소비용보다 낮다면 더 뽑아도 된다는 뜻이다.냅색 문제는 직접 보면 이해가 생각보다 쉬운 편이다. X에는 항상 최소비용이 들어가야 한다. 일단, 아무도 뽑지 않으면 0의 비용이 들어간다. 1명을 뽑을 때는 0명에서 1명을 뽑을 때 비용을 더해주면 된다. 2명을 뽑을때는 1명에서 1명을 더 뽑는 비용 vs 0명에서 2명을 뽑는 비용 중에서 낮은 비용..
🔗 문제 링크https://www.acmicpc.net/problem/1327💡 문제 풀이 및 해석일단, 최소 횟수이고, 모든 경우를 생각해봐야 하기 때문에, BFS로 풀어야 한다.뒤집어 볼 수 있는 위치는 모두 뒤집어본다. 단, 뒤집었을 때 이미 테스트한 경로라면 그 분기는 거기서 끝낸다.이미 테스트한 방식은 set에 저장하여 확인한다.⭐️ 정답 코드 및 설명#include #include #include #include #include using namespace std;int N, K;queue q;set isTest; // 이미 테스트한 항목들은 다시 테스트하지 않기 위한 목록string input() { cin >> N >> K; string str = ""; for (int..