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

https://www.acmicpc.net/problem/31443초코바의 가로 세로 길이가 입력으로 주어지고 초코바를 쪼갰을때 나눠주는 조각의 넓이가 기쁨이고 준영이가 얻는 기쁨은 나눠준 기쁨의 총 곱이다. 이 문제는 백준1437번 수 분해와 완전히 똑같은 문제이다. 구체적인 증명이 어려운 문제인데 결론적으로는 1*3짜리를 가장 많이 만들면 된다. 어떤 자연수(원래 초코바의 넓이)를 분해한 수들(초코바 조각들의 넓이)의 곱(총 기쁨)은 3을 가장 많이 사용했을 때 가장 커진다. 자연수가 아니라면 자연상수인 e(2.718xxx...)의 제곱들이 가장 큰 수를 만든다. 문제의 조건에서 초코바 조각들의 길이는 항상 정수여야한다고 했으므로 e와 가장 가까운 3으로 나누는 경우가 가장 곱들이 커지는 경우가 된다..

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이하로 만들어도 ..