hwooo

https://www.acmicpc.net/problem/2217 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net 풀이 - n개의 로프가 들 수 있는 최대 무게는 (가장 적게 들 수 있는 로프의 중량)*(로프의 개수) - 로프의 최대 중량을 내림차순으로 정렬하고, 다음 로프를 사용했을 때 들 수 있는 중량과 현재 중량을 비교해 최대 중량을 구함 - i번 째 로프까지 중량 < i-1번째 로프까지 중량이면 바로 멈춰도 된다고 생각했는데 아래와 같은 반례가 있을 수 있다 Rope (정렬 후) 15 11 9..

https://www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 풀이 출발할 때는 처음 도시의 기름 가격으로 처음 도로의 길이만큼 가야 하므로 초기값은 Road[0] * Oil[0]로 설정.두 번째 도시에 도착한 이후로는 i번째 도시의 기름 가격이 i-1번째 도시보다 크다면 i-1번째 도시에서 i+1번째 도시에 도달할 수 있을 만큼 주유하면 되므로 해당 로직을 반복하여 제일 오른쪽 도시까지 이동.(제일 오른쪽 도시의 값은 무시 가능) 코드 #in..

https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 풀이 끝나는 시간이 먼저 오는 것을 기준으로, 끝나는 시간이 같다면 시작 시간이 빠른 걸 기준으로 정렬하였다. 시작 시간이 빠른 걸 기준으로 정렬해줘야 하는 이유 더보기 1 2 3 3 2 3 인 경우 정렬하면 1 2 -> 2 3 -> 3 3으로 3개의 회의를 할 수 있기에 끝나는 시간이 같은 경우 시작 시간이 이른 걸 먼저 정렬해야 함 정렬 후, 앞의 회의가 끝나는 시각

https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 풀이 - 문제에서 양수를 사용한다하였으니 문자열의 맨 앞에 부호가 오는 경우는 생각하지 않음 - 음수가 1번 나오면 괄호를 이용하여 뒤의 양수들도 모두 음수로 만들 수 있으므로 음수가 나온 이후의 양수들은 다 빼기로 계산 코드 #include #include #include #include #include using namespace std; int main() { string S; vect..

https://www.acmicpc.net/problem/2211 2211번: 네트워크 복구 첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 회선의 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 컴퓨터와 B번 컴퓨터가 통신 시간이 C (1 ≤ C ≤ 10)인 회선으로 연결되어 있다 www.acmicpc.net 풀이 다익스트라를 이용하여 컴퓨터 간의 최소 연결 시간을 찾는다.이 때 현재 노드의 직전 노드를 같이 저장하며 경로 또한 같이 저장한다. 구한 경로들을 역추적하며 복구할 라인을 찾는다. 이 때, set에 저장하여 중복되는 경로는 제거한다. + 예제의 1-4의 경우 1-2,2-4를 거치는데 이는 1-2까지의 최단거리+2-4의 최단거리이다. 이는 중간에 많은 경로가 존재해도..

https://www.acmicpc.net/problem/5972 5972번: 택배 배송 농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 www.acmicpc.net 풀이 다익스트라를 이용하여 소가 가장 적은 루트를 찾음 코드 #include #include #include #include using namespace std; #define LIMITS 100000000 vector V[50001]; int Cow[50001]; // 최소 시간, 직전 집하장 저장 bool visited[1001]; int Way(int start, int n) { priority_qu..

https://www.acmicpc.net/problem/1719 1719번: 택배 명우기업은 2008년부터 택배 사업을 새로이 시작하기로 하였다. 우선 택배 화물을 모아서 처리하는 집하장을 몇 개 마련했지만, 택배 화물이 각 집하장들 사이를 오갈 때 어떤 경로를 거쳐야 하 www.acmicpc.net 풀이 플로이드-워셜로 풀 수도 있지만 일단 다익스트라 알고리즘을 사용하여 출발지를 바꿔가며 풀었다. 시간이 갱신될 때마다 직전 집하장의 위치도 저장하여, 모든 노드에 대한 최소 시간을 구한 후 역추적했다.이를 테이블에 저장하여 출력함. 코드 #include #include #include #include using namespace std; #define LIMITS 1000000 vector V[1001..

https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 풀이 출발~도착도시까지의 최소 비용은 다익스트라 알고리즘을 이용해 구했다. 현재 저장된 비용은 다른 노드들에 의해 갱신되므로 큐에 저장된 비용보다 작을 수 있다.이런 경우는 실행하지 않아야 시간초과가 나지 않는다.. 이 때, 해당 도시의 직전 도시를 같이 저장해서 경로를 저장했다.경로는 도착도시부터 시작해서 거슬러 올라갔으며, 출발 도시의 직전 도시는 출발 도시의 ..