반응형 전체 글282 백준 14476번 최대공약수 하나 빼기 - C++ 풀이 1. 누적 gcd인 prefix gcd와 suffix gcd 배열을 구해둔다. 2. i번째 수를 제외한 나머지 수들의 gcd는 gcd(prefixGCD[i-1], suffixGCD[i+1])이다. 3. 각 수를 제외하는 모든 경우를 탐색하며 최대공약수가 최대가 되는 경우를 찾는다. 1. 누적 gcd인 prefix gcd와 suffix gcd 배열을 구해둔다. 어떤 수를 제외한 나머지 수들의 gcd를 O(1)에 구하기 위해 누적 gcd 배열을 활용할 것이다. A[0]~A[i] 까지의 최대 공약수는 prefixGCD[i], A[i]~A[N-1]까지의 최대공약수는 suffixGCD[i]라고 할 때, prefix GCD 배열과 suffix GCD 배열을 구해준다. 이 과정의 시간 복잡도는 O(N) 2. i번째 .. 2022. 6. 13. 백준 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. 이전 1 ··· 22 23 24 25 26 27 28 ··· 57 다음 반응형
