반응형 알고리즘207 백준 2251번 물통 - C++ 풀이 1. 모든 상황의 경우의 수는 200*200*200가지이다. 2. 각 상황에서 x물통에서 y물통으로 물을 붓는 모든 경우를 시도하면서 가능한 상황을 모두 구해준다. 1. 모든 상황의 경우의 수는 200*200*200가지이다. 각 물통의 최대 용량은 200이므로 세 물통에 물이 담기는 경우의 수는 N^3가지이다. 2. 각 상황에서 x물통에서 y물통으로 물을 붓는 모든 경우를 시도하면서 가능한 상황을 모두 구해준다. DFS를 이용하여 계속해서 물을 붓는 시뮬레이션을 해준다. DFS(a, b, c) = 현재 세 물통에 a, b, c리터의 물이 담겨있는 상황이라고 하자. 현재 상황에서 물을 붓는 경우는 a -> b, a -> c, b -> a, b -> c, c -> a, c -> b로 총 6가지 이다. 각 경.. 2022. 6. 11. 백준 25287번 순열 정렬 - C++ 풀이 1. 앞에서부터 시작하여 이전 수보다 크거나 같으면서 최대한 작은 수로 채워나간다. 1. 앞에서부터 시작하여 이전 수보다 크거나 같으면서 최대한 작은 수로 채워나간다. 감소하지 않으려면 앞에 있는 수를 최대한 작게 만드는 것이 최적이다. 앞(왼쪽)부터 차례로 i와 N-i+1 중에서 더 작은 수로 채워나가면 된다. 단, 감소하지 않아야 하므로 이전 수보다는 크거나 같아야 한다. 만약 i와 N-i+1 모두 이전 수보다 작다면 감소하지 않도록 만드는 것이 불가능한 경우이다. #include #include using namespace std; bool check(vector& A) { int N = A.size(); for (int i=0; i> T; while (T--) { int N; cin >> N; v.. 2022. 6. 10. 백준 2981번 검문 - C++ 풀이 1. 두 수 a, b를 M으로 나눈 나머지가 같다면 (a-b) % M = 0 2. 두 수 a, b를 M으로 나눈 나머지가 같다면 M의 약수로 나눈 나머지도 같다. 3. A[i+1] - A[i](0 ≤ i < N-1)의 최대 공약수의 약수들이 가능한 모든 M이 된다. 1. 두 수 a, b를 M으로 나눈 나머지가 같다면 (a-b) % M = 0 두 수 a, b를 M으로 나눈 나머지가 r로 같다면, 두 수 a, b는 아래와 같이 나타낼 수 있다. a = M*(a/M) + r b = M*(b/M) + r 위 식에서 아래를 빼면 a-b = M*(a/M-b/M)이므로 (a-b)는 M으로 나누어 떨어진다. 2. 두 수 a, b를 M으로 나눈 나머지가 같다면 M의 약수로 나눈 나머지도 같다. 또한 두 수 a, b를 M.. 2022. 6. 9. 백준 13023번 ABCDE - C++ 풀이 1. 주어진 조건의 ABCDE가 존재하려면 주어진 그래프에 depth가 4 이상인 구간이 있어야 한다. 2. 모든 가능한 DFS를 시도하면서 depth가 4 이상이 되는 경우가 있는지 확인한다. 1. 주어진 조건의 ABCDE가 존재하려면 주어진 그래프에 depth가 4 이상인 구간이 있어야 한다. 주어진 ABCDE의 관계를 나타내면 A -> B -> C -> D -> E이다. 이렇게 5개의 정점이 쭉 연결된 구간이 있다는 것은 그래프의 높이가 4 이상이라는 의미이다. 2. 모든 가능한 DFS를 시도하면서 depth가 4이상이 되는 경우가 있는지 확인한다. 인접한 정점이 여러개일 때 방문 순서에 따라 depth가 달라지기 때문에 모든 경우를 다 시도해보아야 한다. 시작 정점에 따라서도 depth가 달라지기.. 2022. 6. 8. 백준 1083번 소트 - C++ 풀이 1. 그리디 하게 앞자리부터 큰 수로 만들어야 한다. 2. i번째 자리에서 X칸 떨어져있는 수는 X번의 스왑으로 i번째 자리로 끌어올 수 있다. 3. S번 이내의 스왑으로 끌어올 수 있는 가장 큰 수를 앞으로 끌어오기를 반복한다. 1. 그리디하게 앞자리부터 큰 수로 만들어야 한다. 결과가 사전 순으로 가장 뒷서도록 하려면 최대한 앞을 큰 수로 만들어야 한다. 2. i번째 자리에서 X칸 떨어져 있는 수는 X번의 스왑으로 i번째 자리로 끌어올 수 있다. 그리고 i번째 자리(A[i])에서 X칸 떨어져 있는 수(A[i+X])는 최소 X번의 스왑으로 i번째 자리로 끌어올 수 있다. A[i+X]를 A[i+X-1], A[i+X-2], ... 순으로 스왑하면 총 X번의 스왑으로 A[i+X]를 A[i]자리로 끌어오고, .. 2022. 6. 7. 이전 1 ··· 12 13 14 15 16 17 18 ··· 42 다음 반응형
