반응형 Problem Solving242 백준 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. 백준 2294번 동전 2 - C++ 풀이 1. dp(price): 정확히 price원을 만드는데 필요한 동전의 최소 개수 2. dp(price) = min(1 + dp(price - coin[i])) 1. dp(price): 정확히 price원을 만드는데 필요한 동전의 최소 개수 dp(price)를 위와 같이 정의하자. 기저 사례는 price = 0일 때 return 0. 2. dp(price) = min(1 + dp(price - coin[i])) 각 동전의 개수는 무한하므로 price원을 만들기 위해 이번에 사용할 동전만 골라주면 된다. i번째 동전을 사용하기로 했을 때 dp(price) = 1 + dp(price- coin[i]). i = 0~(N-1)까지 각 동전을 고르는 모든 경우를 탐색한 뒤, 그중 최솟값을 찾으면 된다. #inclu.. 2022. 6. 5. 이전 1 ··· 19 20 21 22 23 24 25 ··· 49 다음 반응형
