private static void life()

예제 입력 1 3 2 1 65 5 23 2 99 10 2 예제 출력 1 164 - 두 가지 방법으로 풀이가 가능하다. 1) 각각의 보석을 기준으로, 보석이 어떤 가방에 들어가면 좋을까? 가격이 높은 순으로 들어갈 수 있는 가장 작은 가방에 넣고 그 가방을 지운다. 2) 각각의 가방을 기준으로, 어떤 보석이 들어가면 좋을까?? [ 풀이 1) ] #include #include #include #include const int MAX_SIZE = 300000; using namespace std; class Jewel { public: int m; // 무게 int v; // 가격 }; multiset bag; int N; int K; int main(void) { scanf("%d %d", &N, &K);..

* set / multiset 모두 BST(Binary Search Tree) 형태의 자료 구조이다. [ Set ] - 중복을 허용하지 않는 자료 구조. (중복을 허용하려면 multiset을 사용해야 함.) - 원소들은 자동으로 정렬된다. (insert) #include #include int main(void) { using namespace std; set setTest; setTest.insert(3); setTest.insert(4); setTest.insert(1); setTest.insert(2); setTest.insert(2); setTest.insert(4); setTest.erase(5); printf("%d\n", *setTest.find(4)); // 4 if (setTest.fin..

예제 입력 1 3 HHT THH THT 예제 출력 1 2 https://www.acmicpc.net/problem/1285 1285번: 동전 뒤집기 첫째 줄에 20이하의 자연수 N이 주어진다. 둘째 줄부터 N줄에 걸쳐 N개씩 동전들의 초기 상태가 주어진다. 각 줄에는 한 행에 놓인 N개의 동전의 상태가 왼쪽부터 차례대로 주어지는데, 앞면이 위를 향하도록 놓인 경우 H, 뒷면이 위를 향하도록 놓인 경우 T로 표시되며 이들 사이에 공백은 없다. www.acmicpc.net - 각 행/열 별로 동전을 뒤집을 수 있다. 행렬/전구와 스위치 문제와 유사 - 각 동전의 상태에 영향을 미칠 수 있는 동작은 2가지 이다. (그 행에 속하는 행 뒤집기, 그 열에 속하는 열 뒤집기) - 그런데, 이미 모든 행에 대해서 뒤..

예제 입력 1 3 000 010 예제 출력 1 3 https://www.acmicpc.net/problem/2138 2138번: 전구와 스위치 N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져 있는(1) 상태와 꺼져 있는 (0) 상태 중 하나의 상태를 가진다. i(1

예제 입력 1 3 4 0000 0010 0000 1001 1011 1001 예제 출력 1 2 https://www.acmicpc.net/problem/1080 1080번: 행렬 첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다. www.acmicpc.net - 여기서, A행렬에서 모두 가능한 3x3 Flip 연산을 하느냐/하지 않느냐로 Brute Force를 돌리면 2^NM (실제로는 2^(N-2)(M-2)) 이라는 어마어마한 시간 복잡도가 나오기 때문에 이 방법으로는 해결 불가능하다. - 여기서, 핵심은 (0,0) 부분이 다르다면, (0,0) 부분을 변경하도록 해야 하는..

예제 입력 1 5 3 1 4 3 2 예제 출력 1 32 - 그리디 알고리즘으로 접근하고자 할 때는 반례를 찾고, 최적이 맞다고 생각되면 증명이 필요하다. - 정답은 적게 걸리는 시간으로 정렬하여 푼다. - 증명은 아래와 같다. : t1 ~ t5는 1~5번 사람이 돈을 인출하는데 걸리는 시간이며, P1 ~ P5는 각 사람이 돈을 인출 완료하기까지 기다려야 하는 시간, 각 번호는 t가 작은 순으로 오름차순으로 정렬되어있다고 가정. : P1 = p1 : P2 = p1 + p2 : P3 = p1 + p2 + p3 : .... : P5 = p1 + ... + p5 Psum = 5*p1 + 4*p2 + ... + p5 따라서 p1이 작을수록 유리하다. #include constexpr int MAX_COUNT = ..

예제 입력 1 11 1 4 3 5 0 6 5 7 3 8 5 9 6 10 8 11 8 12 2 13 12 14 예제 출력 1 4 https://www.acmicpc.net/problem/1931 1931번: 회의실배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net - 정답은 회의가 일찍 끝나는 시간 기준으로 그리디 알고리즘으로 풀 수 있다. - 회의 끝나는 시간으로 정렬하여 순서대로 처리하여 풀 수 있는데, 주의할 점은 회의가 끝나는 시간이 같을 경우 회의가 일찍 시작하는 순으로 정렬하여야 한다. 회의 시작시간과 끝시간이 같은 경우를 처리하여야 하기 때문인데, 이를 구현하지 않으면 아래 케이스를 풀 수 없다. 1 1 1 2

예제 입력 1 10 4200 1 5 10 50 100 500 1000 5000 10000 50000 예제 출력 1 6 예제 입력 2 10 4790 1 5 10 50 100 500 1000 5000 10000 50000 예제 출력 2 12 https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net - 이 문제의 조건에서는 주어지는 동전이 Ai는 Ai-1의 배수라고 했으므로, 그리디 알고리즘을 ..

예제 입력 1 7 392 예제 출력 1 +*+ 예제 입력 2 7 256 예제 출력 2 /+*** 예제 입력 3 4 256 예제 출력 3 ** 예제 입력 4 7 7 예제 출력 4 0 예제 입력 5 7 9 예제 출력 5 -1 예제 입력 6 10 1 예제 출력 6 / https://www.acmicpc.net/problem/14395 14395번: 4연산 첫째 줄에 정수 s를 t로 바꾸는 방법을 출력한다. s와 t가 같은 경우에는 0을, 바꿀 수 없는 경우에는 -1을 출력한다. 가능한 방법이 여러 가지라면, 사전 순으로 앞서는 것을 출력한다. 연산의 아스키 코드 순서는 '*', '+', '-', '/' 이다. www.acmicpc.net - 문제의 조건에서 s와 t의 최대값이 10의 9승이므로 (=10억) 배..

예제 입력 1 5 RRRBB GGBBB BBBRR BBRRR RRRRR 예제 출력 1 4 3 https://www.acmicpc.net/problem/10026 10026번: 적록색약 문제 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 www.acmicpc.net - 동일한 색깔끼리 BFS를 이용하여 그룹..