본문 바로가기

Algorithm98

8980 - 택배(greedy) www.acmicpc.net/problem/8980 8980번: 택배 입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이 www.acmicpc.net - 운반거리가 짧은 구간. 즉 도착지가 가까운 순으로 배송정보를 정렬하고, 지나가는 마을마다 담을 수 있는 박스의 최대치는 답에 더해나가는 그리디 방식으로 접근했다. #include #include #include using namespace std; // 도착지가 가까운 순으로 배송정보를 정렬하고 // 트럭이 지나가는 마을마다 트럭이 상자를 실을 수 있는 최대치를 모두 더한다 // 경로상에.. 2021. 4. 1.
[boj]15723 - n단논법(Floyd Warshall, string 입출력) www.acmicpc.net/problem/15723 15723번: n단 논법 m개의 줄에 걸쳐 각 줄에 결론이 참인지 거짓인지 출력하라. 참일 경우 T, 거짓일 경우 F를 출력하라. 알 수 없는 경우도 거짓이다. 답은 필히 대문자로 출력해야 한다. www.acmicpc.net - 플로이드 와샬 알고리즘을 알고 있으면 쉽게 풀 수 있는 문제이다. - 플로이드 와샬을 통해서 입력을 통해 주어진 논증 외에도 2~n단 논법을 통해서 징검다리 식으로 증명할 수 있는 논증에 대해서 차례차례 DP 스타일로 증명해 나갈 수 있다. - string 전체를 입력으로 받을 때 getline(cin, string)을 쓰는데 이전에 cin으로 입력을 받았다면 꼭 flushing을 해서 버퍼에 남아있는 '\n'을 제거 해줘야한.. 2021. 4. 1.
[boj] 11657 - 타임머신(shortest path, bellman-ford) www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 최단거리 문제이다. 간선의 가중치가 음수인 케이스가 있으므로 다익스트라 알고리즘으로 풀 수 없고, 벨만포드 알고리즘으로 풀어야 한다. 노드가 n개일 때, 최대 n-1개의 간선에 대하여 최단거리를 계산해준다. 따라서 시간복잡도는 n개의 노드에 대해서 n-1개의 간선을 검사하므로 O(V*E) = O(V^3)이 나온다. 다만 음수사이클이 있는 경우를 계산하.. 2021. 3. 29.
[boj] 8980 - 택배(greedy) www.acmicpc.net/problem/8980 8980번: 택배 입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이 www.acmicpc.net - 그리디 방식으로 접근했다. 출발지에서 도착지가 가까운 도시의 박스를 옮기는 것이 최적의 해를 구할 수 있다. - 도착지가 가까운 순으로 배송정보를 정렬하고, 트럭이 지나가는 마을마다 트럭이 상자를 실을 수 있는 최대치를 모두 더한다 - 경로상에서 트럭이 실을 수 있는 최대치는 (최대용량 - 이미 실고 있는 박스) 이다 #include #include #include using namesp.. 2021. 3. 29.

티스토리툴바