Doby's Lab

https://www.acmicpc.net/problem/1210 1210번: 마피아 첫 줄에는 톨게이트의 개수 n과 고속도로의 개수 m이 주어진다.(1 ≤ n ≤ 200, 1 ≤ m ≤ 20000) 톨게이트의 번호는 1부터 n까지로 주어진다고 할 때, 다음 줄에는 마피아의 시작점과 도착점이 주어진 www.acmicpc.net Solved By: MFMC 각 정점에 대해 cost가 있기 때문에 Max Flow를 흘리기 위해 Edge의 비용은 INF로 처리하고, 정점 분할을 사용하여 in과 out사이에 비용을 할당하여 네트워크 모델링을 해야 했습니다. 1) 이번 문제에서 헷갈리면서 풀었던 것이 in에는 들어가기만 해야 하기 때문에 다른 node out으로 in을 인접 배열로 연결만 해주고, capacity..

https://www.acmicpc.net/problem/14286 14286번: 간선 끊어가기 2 정점 n개, m개의 간선으로 이루어진 무방향 그래프가 주어진다. 그리고 그래프 내에 있는 m개의 가중치 간선의 정보가 있는 간선리스트가 주어진다. 간선리스트에 있는 간선 하나씩 그래프에 제 www.acmicpc.net Solved By: MFMC MFMC(Max Flow Min Cut)에 대해 시작하기 좋은 문제였습니다. Max Flow와 Min Cut의 비용이 동치인 것을 알고 Max Flow를 구현하여 풀 수 있습니다. #include #include #include #define MAX 501 #define INF 1e9 using namespace std; vector adj[MAX]; int c[..

https://www.acmicpc.net/problem/2670 2670번: 연속부분최대곱 첫째 줄은 나열된 양의 실수들의 개수 N이 주어지고, 그 다음 줄부터 N개의 수가 한 줄에 하나씩 들어 있다. N은 10,000 이하의 자연수이다. 실수는 소수점 첫째자리까지 주어지며, 0.0보다 크거나 www.acmicpc.net Solved By: DP 풀면서 Brute-Force 한 느낌이 들었습니다. 모든 시작점부터 n까지 다 곱해가면서 시작점마다 최댓값을 구하고, 또한 그 최댓값 N개 중에서도 최댓값을 구해야 합니다. #include #define MAX 10001 using namespace std; double arr[MAX]; double cache[MAX]; int n; int main(){ io..

https://www.acmicpc.net/problem/1965 1965번: 상자넣기 정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 www.acmicpc.net Solved By: LIS 몇 달만에 풀어본 LIS 문제였습니다. 본인 이전에 작은 값이 없으면 그 값은 1을 가진다는 걸 인지 못 한 채로 계속 틀렸었습니다. 그걸 인지하니 바로 풀리더군요. #include #define MAX 1001 using namespace std; int n; int arr[MAX]; int cache[MAX]; int main(){ cin >> n; for(int i = 1;..

https://www.acmicpc.net/problem/17484 17484번: 진우의 달 여행 (Small) 첫줄에 지구와 달 사이 공간을 나타내는 행렬의 크기를 나타내는 N, M (2≤ N, M ≤ 6)이 주어진다. 다음 N줄 동안 각 행렬의 원소 값이 주어진다. 각 행렬의 원소값은 100 이하의 자연수이다. www.acmicpc.net Solved By: DP (Recursive Call) Bottom-Up 방식의 DP로 풀려했으나 지나온 방향을 중복적으로 선택하면 안 되는 것을 구현을 못 해서 Recursive Call의 형태로 코드를 짜야했습니다. 그러나, 짜기가 꽤 어려워 공부를 해보았습니다. (https://oriburger.tistory.com/entry/PS%EC%99%84%EC%A0%..

https://www.acmicpc.net/problem/15624 15624번: 피보나치 수 7 첫째 줄에 n번째 피보나치 수를 1,000,000,007으로 나눈 나머지를 출력한다. www.acmicpc.net Solved By: DP, map n의 범위가 [1, 1,000,000]으로 너무 큽니다. 배열을 선언할 수도 없기 때문에 map을 사용하여 dp를 돌려봤습니다. #include #include #define MOD 1000000007 using namespace std; int n; map m; int fibo(int n){ if(n == 0) return 0; else if(n == 1 || n == 2) return 1; else{ if(!m[n]) return m[n] = (fibo(n ..

https://www.acmicpc.net/problem/14606 14606번: 피자 (Small) 예제1의 입력이 1이므로, 게임 시작부터 갑이 분리할 수 있는 피자탑이 없습니다. 따라서 갑이 얻는 즐거움은 0입니다. 예제2의 정답 3은 다음과 같은 과정을 통해 얻어집니다. 먼저 놀이를 시작 www.acmicpc.net Solved By: DP cache 배열에다가 n층일 때, 가지는 즐거움의 총합을 넣을 겁니다. n을 어떻게 나누었을 때, 그 두 값이 최댓값이 되는지는 몇 개만 테스트해봐도 반으로 나누었을 때가 최댓값인 게 나타납니다. 즉, 점화식은 다음과 같이 나타날 수 있습니다. int v = i / 2; // 반으로 나누었을 때, 서로의 곱이 가장 크다. cache[i] = (v * (i - ..

https://www.acmicpc.net/problem/18769 18769번: 그리드 네트워크 재현이는 그리드 네트워크 컨설팅 회사를 운영하고 있다. 어떤 회사의 데이터 서버가 격자 형태의 그래프로 주어졌을 때, 최소의 비용을 들여서 전용 통신망을 설치하려고 한다. 이때, 전용 통 www.acmicpc.net Solved By: MST, Implementation 간단한 MST 문제였지만 좌표를 어떻게 모델링하여 코드를 짤지는 조금 어려웠습니다. 예를 들어 2행 3열의 네트워크가 있으면 5번 노드를 나타낼 때, (i - 1) * c + j (5번 노드는 2행 2열)과 같이 나타내려 했는데 행간과 열간의 가중치를 할당하기 어려웠습니다. 그래서, 직관적으로 구현을 하였습니다. (보기 흉한 코드이지만..)..