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  ..

https://www.acmicpc.net/problem/24025돌의 정령의 무리의 키가 4 1 5 2 3 이라면 왼쪽수터 시야 점수는 2 0 INF 0 INF 가 된다. 자신의 무리보다 키가 큰 무리 전까지의 돌의 정령 무리 수가 시야 점수가 된다. 문제에서 돌의 정령 무리수와 동일한 개수만큼의 숫자가 주어진다. 주어진 숫자가 A(A>0)일 경우 해당 숫자가 주어진 인덱스의 돌의 정령의 시야점수가 A이상이 되도록, 주어진 숫자가 -A(-A ★Point1. 마지막에 배치되는 돌의 정령의 시야점수는 항상 INF이다.2. 돌의 정령의 무리가 N~1까지 내림차순으로 배치되면, 모든 돌의 정령의 무리의 시야점수는 INF이다. 돌의 정령의 시야점수가 딱 A가 되게 만드는 것이 아니라 A이상 -A이하로 만들어도 ..