https://www.acmicpc.net/problem/2405 중위값과 평균값이 세 개 이상이 되도록 하는 숫자 3개를 고르는 문제이다.어떻게 하면 중위값과 평균값이 가장 커질까를 생각해야하는데숫자들을 정렬한 후에 1. 0번째 인덱스의 숫자를 고정시키고 이후 i번째 i+1번째 숫자를 선택하여 차이가 가장 커지는 순간을 구함2. n-1번째 인덱스의 숫자를 고정시키고 이후 i번째 i+1번째 숫자를 선택하여 차이가 가장 커지는 순간을 구함 1번과 2번을 모두 수행한 결과 나온 가장 큰 차이가 답이 된다. #include #include #include #include using namespace std;int main() { int n, avg, ans, tmp; cin >> n; vector v(n); ..

https://www.acmicpc.net/problem/19846constructive 문제에 익숙하지 않으면 숨이 턱 막히는 문제일 수 있다.constructive는 문제를 한 발짝 뒤에서 바라볼 수 있어야 한다. 이번 문제는 각 구간에 대해 홀수번 나오는 문자가 단 한 개인 예시를 만드는 문제이다.구간도 여러개이고, 어떤 구간이 테스트 케이스로 주어질지 모르는데 그리디처럼 접근하면 코드가 매우 길어지고난이도도 많이 올라간다. Greedy 사고: 주어진 입력을 잘 활용하여 최적의 솔루션을 찾는 것즉, 예시로부터 귀납적으로 생각해서 일반화하는 느낌Constructive 사고: 입력과 같은 특정 구간이 아니라 어떠한 구간이 입력으로 주어지더라도 가능한 경우를 생각하는 것즉, 문제 전체를 아우르는(?) 답..

https://www.acmicpc.net/problem/13018이 문제는 특이한 수열 A를 찾는 문제이다. 특이한 수열의 성질은 다음과 같다.수열 A의 길이는 n1이상 n이하의 정수가 빠짐없이 모두 등장해야 하며, 각 수는 한번만 등장해야함1 ≤ i ≤ n 인 i에 대해 gcd(i, A[i]) > 1 을 만족하는 i가 정확히 k개여야함n, k 가 주어졌을 때, 특이한 수열을 아무거나 하나 구해보자.gcd(i,A[i]) > 1을 만족하는 수는 i == A[i]이면 된다.따라서 i == A[i]를 만족하는 수를 k개 출력하면 되고 나머지 인덱스와 원소의 관계는 서로소되야 한다.i와 A[i]의 차가 1이거나 원소에 1이 있으면 항상 gcd(i,A[i]) = 1(서로소)을 만족한다. 1~N까지의 원소를 활용..

https://www.acmicpc.net/problem/30297 순열P를 irreducible한 순열로 만드는 문제이다.reducible의 정의로는 배열의 앞에서 하나씩 원소를 떼서 부분집합을 만들었을 때 순열을 만족하면 reducible한 순열이다.(단, 자기 자신은 제외) irreducible한 순열이 되기 위해서는...i번째 원소까지의 최대값이 i보다 커질수 있도록 스왑하면서 이동하면 된다.입력으로 주어지는 N의 값의 합이 500000이하인 것이 보장되므로 테스트 케이스 하나당 O(N)으로 해결하면 된다. #include #include #include #define endl "\n"using namespace std;int t, n, m, tmp;int main() { ios_base::syn..

https://www.acmicpc.net/problem/13955최대 n번의 operation을 이용해서 비트의 가중치가 2n이상이 되도록 하게 하는 문제다.주어지는 비트의 길이가 3n이므로 가중치가 2n이 되기 위해서는최소 3번의 비트마다 한번 flip마다 가중치가 2씩 더해져야 한다. flip한번으로 3개의 비트의 가중치가 가장 커지는 경우를 보면(이웃 비트로 인한 가중치)000 → 최대 가중치 1001 → 최대 가중치 2010 → 가중치가 이미 2로 최대임011 → 최대 가중치 2100 → 최대 가중치 2101 → 가중치가 이미 2로 최대임110 → 최대 가중치 2 111 → 최대 가중치 1 000과 111을 제외하고 모두 이웃 가중치를 2로 만들 수 있다. (본인 포함하면 3)따라서 비트를 3개..

https://www.acmicpc.net/problem/31577 1부터 20까지의 수가 15개의 컴퓨터 중에서 최소 6개의 컴퓨터에 들어가 있는 경우를 찾아내야 하는 문제다.당연히 5개의 컴퓨터까지 랜섬웨어에 걸릴 수 있으므로 최소 6개가 들어가야 한다.또한 한 컴퓨터에는 최대 8개의 파일만 들어갈 수 있다. 의도된 문제겠지만15 × 8 = 20 × 6 으로 개수도 딱 맞아 떨어진다.120까지 돌면서 i%20+1을 배열에 저장해두고 8개씩 끊으면 끝이다. 코드는 다음과 같다.#include #include #include #define endl "\n"using namespace std;int main() { vector bit; int arr[8]; for(int i = 0; i  ..