🔗 문제 링크https://www.acmicpc.net/problem/1197💡 문제 풀이 및 해석문제에서 최소 스패닝 트리라고 나와 있으므로 같은 방식으로 풀면 좋다.사실 최소 스패닝 트리가 기억이 잘 나지 않지만, 일단 트리 형식을 갖추면서 가중치가 가장 적은 트리를 만들어야 한다는 것을 알 수 있다.그러면 최대한 낮은 비용의 간선부터 연결해야 한다.단, 간선을 연결할 때, Cycle이 생기면 안된다. => Root가 같은 것들끼리는 연결해서는 안된다.따라서 비용을 오름차순으로 정렬하고 4번을 지키면서 낮은 것들을 계속 연결해가면 된다.단, 매번 부모를 계속 찾을 수 없으므로 매번 현재 나의 Root가 무엇인지 업데이트 해준다.⭐️ 정답 코드 및 설명#include #include #include..
baekjoon
🔗 문제 링크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..
🔗 문제 링크https://www.acmicpc.net/problem/1188💡 문제 풀이 및 해석최대공약수를 구하는 문제이자 패턴 문제이다. 모든 소시지를 합쳐서 1개로 만들고 균일하게 자른다고 생각하면 된다. 이 때, 소시지를 합치는 자리를 칼질하는 경우만 카운팅을 안하면 된다.예제 2번 케이스에서 3 4 => 인당 3/4가 필요하다는 뜻이고, 이는 소세지 3개를 이어 붙여서 1개로 만든 다음에 4등분하면 된다는 뜻이다. 따라서 3번만 자르면 된다.다시 예제 1번 케이스를 보자 2 6 이 들어오고 인당 2/6이 필요하다. 이는 소세지 2개를 이어 붙여서 1개로 만든 다음에 6등분하면 된다는 뜻인데, 그러면, 총 5번의 칼질 중 1번의 칼질은 카운팅할 필요가 없다. 이는 최대공약수로 나타낼 수 있다..
🔗 문제 링크https://www.acmicpc.net/problem/1034💡 문제 풀이 및 해석처음에는 50X50의 문제여서 완전탐색으로 풀 수 있는 문제라 생각했는데, 1000번의 열의 스위치를 킬 수 있다는 선택지 때문에, 2^50의 가짓수라 모든 경우를 찾아볼 수 없는 문제였다.문제의 조건을 보았을 때, K번을 반드시 눌러야 하므로 예제에서 열이 1개일 때, 짝수번이면 변화가 없는 것을 알 수 있다. 이 점에 유의해야 한다.모든 경우를 찾을 수 없다면, 경우를 줄여야 하는데, 이때, 패턴을 찾는 것이 그 방법이다. 예를 들어서 100 100 101 110 이런 식이라고 하자. 100과 101, 110은 같은 열의 솟자가 바뀌기 때문에 최종적으로 모두 1인경우가 나올 수가 없다. 따라서 100..
🔗 문제 링크https://www.acmicpc.net/problem/11054문제 링크가 제대로 달리지 않아 링크 남겨두었습니다.💡 문제 풀이 및 해석어떤 특정한 수를 기준으로 양쪽에서 증가하는 수열을 찾아야 한다.N의 범위가 1000 이므로 한번에 검사하는 것이아닌 왼쪽과 오른쪽으로 증가하는 수열을 따로 찾아도 된다.한쪽으로 증가하는 부분 수열을 찾는 방법은 아래와 같다.현재 index가 K라면, 0~K-1 까지의 수들을 모두 탐색한다.이 때, K보다 작은 수들을 찾는다.그 중에서 DP[찾은 수] + 1 > DP[K]라면 증가하는 부분 수열이므로 업데이트 해준다.찾은 모든 수들에 대해서 3번을 반복하면 DP[K]가 최댓값을 갖는다.위 방식으로 좌우를 했을 때, rightDp와 leftDp를 더한다..
🔗 문제 링크 14728번: 벼락치기ChAOS(Chung-ang Algorithm Organization and Study) 회장이 되어 일이 많아진 준석이는 시험기간에도 일 때문에 공부를 하지 못하다가 시험 전 날이 되어버리고 말았다. 다행히도 친절하신 교수님께서 아래와www.acmicpc.net💡 문제 풀이 및 해석가치에 따라서 결정하는 냅색 문제이다.우리가 최대로 가져가야 하는 것은 점수이고, 그 비용은 시간이 된다.최대로 가져갈 수 있는 점수는 dp[T]에 있다. 이 때, 역순으로 다이나믹 프로그래밍을 진행한다.dp는 그 시간대의 최대값이므로 검사할 시간이 t라면, dp[t] = max(dp[t], dp[t - time] + score)는 t-time 이 그 시간에서 최대이고 현재 값을 더하면..
