개발조아

문제 링크 : https://www.acmicpc.net/problem/21278 21278번: 호석이 두 마리 치킨 위의 그림과 같이 1번과 2번 건물에 치킨집을 짓게 되면 1번부터 5번 건물에 대해 치킨집까지의 왕복 시간이 0, 0, 2, 2, 2 로 최소가 된다. 2번과 3번 건물에 지어도 동일한 왕복 시간이 나오지만 더 www.acmicpc.net 건물의 개수가 최대 100개고 모든 건물사이의 최단 거리를 구해놓으면 쉬우므로 플로이드 와샬로 해결하였다. 입력으로 반은 건물로 배열을 구성하는데 가중치는 1로 넣자 그리고 플로이드 와샬로 각점에 대해서 최단거리를 구해 놓자. 다음 치킨집을 지으려는 매장 두곳을 골라야한다. 이중포문으로 골라도 되지만 귀찮으니 combinations을 사용했다. 두개의 ..

문제 링크 : https://www.acmicpc.net/problem/14938 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 각 노드에서 출발하여 정해진 가중치 이내로 갈 수 있는 노드들이 가지고 있는 값의 합의 최대값을 구하는 문제이다. 모든 노드에서 각 노드로 최단거리를 구해서 그 길이가 m 이하인 것들의 아이템수의 합을 구하고 그중 최대값을 구하면 된다. 모든 노드에 대해서 최단거리는 플로이드와샬과 다익스트라로 해결할 수 있다. 해당 문제는 노드의 개수가 최대 100개 이므로 플로이드와샬로 해결 가능하다...