답은 알고리즘 뿐이야!

문제 출처 : www.acmicpc.net/problem/1525 풀이 : BFS 문제입니다. 메모리 제한이 24메가로 작습니다 그렇기에 9개의 칸을 0~8의 값인지 9차원 배열로 판단할 시에 메모리 초과가 뜨게 됩니다. 그렇기에 [3][3] 배열을 long long 형 변수에 매핑시켜 그 값을 중복 체크 하시면 됩니다.

문제 출처 : https://www.acmicpc.net/problem/2342 문제 풀이 : DP문제입니다. cache[idx][l][r] : idx번째 지시사항이고 왼발이 l번째칸 오른발이 r번째 칸에 있을때의 사용된 최소힘 이라고 두고 cache를 쌓으시면 됩니다. 칸별로 이동시 드는 힘은 dir[5][5] 배열을 선언하여 편하게 처리하도록 합시다.

문제 출처 : https://www.acmicpc.net/problem/14725 풀이 : 문자열로 트리를 구성하는 문제입니다. 문제에서 주어지는 인풋 대로 트리를 채워나가시되 이진 트리가 아닌 N진 트리로 구성하시면 됩니다. 저는 정렬을 하기 위해 처음부터 사전순으로 비교하여 현재 인덱스의 스트링이 사전순으로 뒤에있으면 그 자리에 삽입하고 나머지를 뒤로 푸쉬해주는 방식으로 하였습니다.

문제 출처 : https://www.acmicpc.net/problem/1031 풀이 : Maximum Flow 문제입니다. 아래의 조건에 따라 푸시면 됩니다. 1. A팀의 경기수 총합 != B팀의 경기수 총합 => -1 2. A팀의 경기수 총합 != Maximum Flow => -1 3. A팀의 경기수 총합 == Maximum Flow => 사전순 정렬 이문제의 핵심은 3번 사전순 정렬인데 사전순 정렬은 엣지 하나를 고르고 엣지와 동일한 시작점에서 동일한 끝점으로 갈수있는 다른 플로우가 있는지 찾은 후 있으면 엣지의 플로우를 지워주고 경로에 Flow를 흘려주시면 됩니다. 단 찾을때 정렬을 해야하기 때문에 시작점과 끝점의 범위에 주의해야합니다. 만약 인풋이 2 2 1 1 1 1 일때, 1->3, 2->4..

문제 출처 : https://www.acmicpc.net/problem/3640 풀이 : MCMF 문제입니다. 1 을 source, V 를 sink로 잡고 mcmf를 해주시면 되는데 조건중에 정점 중복이 없다라는 말이 있으므로 정점 분할을 하고 V번 정점에서 V ' 번 정점으로 가는 Capacity를 2로, S번 정점에서 S ' 번 정점으로 가는 Capacity를 충분히 준 후 MCMF를 돌리시면 됩니다. 아래는 2번째 인풋을 모델링 한 그림입니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 ..

문제 출처 : https://www.acmicpc.net/problem/2367 풀이 : 네트워크 플로우 (Maximum Flow) 문제입니다. 파티에 N명의 사람이 오고 D개의 음식을 준비해야하는데 한 사람당 음식을 K개 준비할 수 있고 같은 음식은 1개만 준비할 수 있습니다. 따라서 다음과 같이 모델링 할 수 있습니다. 1. Source에서 사람으로 K만큼의 Capacity를 가진 Edge를 연결 2. 사람에서 각 사람당 준비할 수 있는 음식으로 1만큼의 Capacity를 가진 Edge를 연결 (한개의 음식은 한사람당 하나만 들고갈수 있으므로) 3. 각 음식에서 Sink로 가져올 수 있는 갯수만큼의 Capacity를 가진 Edge를 연결 예제의 경우를 네트워크 플로우로 모델링 하면 아래와 같은 모형이..

문제 출처 : https://www.acmicpc.net/problem/13511 풀이 : LCA 문제 입니다. 첫번째 쿼리를 처리하기 위해선 아래와 같이 LCA를 구하기 위해 전처리를 할때 cost 값도 같은 점화식으로 구해주시면 되고, for (int i = 1; depth[ni] > 1 > b >> c; if (a == 1) cout

문제 출처 : https://www.acmicpc.net/problem/14247 풀이 : 그리디(탐욕법) 문제입니다. 나무를 최대로 잘라가는 문제입니다. 따라서 나무가 자라는 길이가 최소인 애들이 제일 밸류가 떨어지므로 길이가 최소인 애들부터 잘라서 들고가면 됩니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 #include #include #include using namespace std; typedef long long ll; typedef pair p; int n; p arr[100000]; priority_queue q; ll ret; int main() { ios::sync_with_stdio(fals..

문제 출처 : https://www.acmicpc.net/problem/3006 풀이 : 세그먼트 트리 문제입니다. 각 숫자가 자신의 자리를 찾아가는데 항상 작은 숫자는 왼쪽 큰 숫자는 오른쪽으로 가기 때문에 홀수번째 일때는 왼쪽숫자의 갯수, 짝수번째는 오른쪽 숫자의 갯수로 옮기는 횟수를 쉽게 구할 수 있습니다. 각 숫자의 위치를 따로 저장해주고 세그먼트 트리에 각 숫자의 위치의 값을 1로 채웁니다. 그다음 세그먼트 트리를 활용하여 1. 홀수번째 : 찾으려는 값의 왼쪽 범위의 구간합 2. 짝수번째 : 찾으려는 값의 오른쪽 범위의 구간합 을 구하시면 됩니다. 구하신 후에는 찾으려는 값의 세그먼트 트리에 저장된 정보를 0으로 바꾸고 업데이트 시키시면 됩니다. 1 2 3 4 5 6 7 8 9 10 11 12 ..

문제 출처 : https://www.acmicpc.net/problem/18111 풀이 : 완전 탐색 문제입니다. 각 높이별로 블록이 몇 개 있는지 저장한 후 각 높이를 탐색하여 조건에 맞게 계산한 후 최댓값을 뽑아내면 됩니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 #include using namespace std; int n, m, b, a[257], result = 1e9, hei, i, j, ret, bb; int main() { ios_base::sync_with_stdio(false); cout.tie(0); cin.tie(0); for (cin >> n >> m >> b; i > ..