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/74534개의 배열 A,B,C,D가 주어졌을 때 해당 배열들에서 수를 하나씩 선택했을 때 선택한 수들의 합이 0인 경우가 몇가지인지 구하는 문제다.나이브하게 4중포문으로 구현이 가능하긴 하지만 아무리 제한시간이 12초라도 4000을 네 번 곱하면(N⁴) 시간초과가 당연하다.(N = 1억에 1초로 생각하면 된다) 아이디어는 선형대수학을 떠올렸는데 선형대수학에서 ABx = C의 방정식을 풀때 행렬 AB를 구하는 과정에 O(N³)이 걸리기 때문에 Bx를 치환함으로써 O(N²) 두번으로 문제를 해결했었다. 이 문제도 4중포문 대신 AB의 모든 경우의 수를 계산하고(O(N²)), CD의 모든 경우의 수를 계산해서(O(N²)) AB배열과 CD배열을 투포인터로..

https://www.acmicpc.net/problem/2655벽돌은 회전시킬 수 없다. 즉, 옆면을 밑면으로 사용할 수 없다.밑면의 넓이가 같은 벽돌은 없으며, 또한 무게가 같은 벽돌도 없다.벽돌들의 높이는 같을 수도 있다.탑을 쌓을 때 밑면이 좁은 벽돌 위에 밑면이 넓은 벽돌은 놓을 수 없다.무게가 무거운 벽돌을 무게가 가벼운 벽돌 위에 놓을 수 없다.위의 조건을 만족하면서 가장 높게 탑을 쌓아야한다. 입력으로 주어지는 벽돌의 개수가 100개 이하이므로 모든 경우의 수를 다 훓어보기에 충분하다. 훓을때 고려해야할 조건이 무게가 높은 블럭, 밑면적이 큰 블럭이 밑에 쌓여야만 한다.본인은 밑면적 순으로 정렬해서 탐색할때 밑면적이 큰 놈이 밑으로 오게 하고 무게 조건은 if문으로 처리했다. Dp[i]가 ..