G4

🔗 문제 링크https://www.acmicpc.net/problem/20056💡 문제 풀이 및 해석시뮬레이션 문제인 만큼 문제의 최적화보다는 설명한 그대로 구현해야 한다. 주의할 점만 적어놓겠습니다.파이어볼이 조건에 맞게 이동한다.1-1. 조건대로 이동할 때, 파이어볼이 맵 밖으로 나가는 경우는 반대쪽에서 나오게 설정해야 한다.1-2. 파이어볼이 이동하기 전에 기존에 맵에 저장되어 있던 파이어볼의 정보는 초기화 시켜줘야 한다.이동한 파이어볼은 분열한다.2-1. 분열하면서 주의할 점은 모두 짝수 or 홀수 방향인 것을 정해줘야 한다는 점이다. (따로, 체크를 해야함)2-2. 한 번만 이동해도 분열은 시켜준 뒤에 질량을 측정해야 한다.이 과정을 K번 반복한다.⭐️ 정답 코드 및 설명#include #i..

🔗 문제 링크https://www.acmicpc.net/problem/1277💡 문제 풀이 및 해석1과 N이 만나야 한다.두 발전소 사이의 거리(좌표상 거리)가 M미만이면, 두 발전소 사이에는 간선이 있다.이미 이어진 발전소는 길이가 0인 간선이 있다고 생각한다.이제 1에서 시작하는 평범한 bfs문제가 된다. (최적화를 하고 싶다면 다익스트라로 풀어야한다.) vector > > edge(1001); // 발전소, 거리 이 부분을 내부를 vector>> edge(1001) // 거리, 발전소 이와같이 바꾸면 짧은 거리부터 찾아가면서 실제로 더 빠를 것 같다.⭐️ 정답 코드 및 설명#include#include#include#include#define INF 98754321using namespace s..

🔗 문제 링크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/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..