취업 준비 및 일상

https://www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 www.acmicpc.net 나의 접근 방법 N = 10000, M = 100000이므로 O(N^2)보다 작은 시간복잡도를 갖는 풀이가 있을 거라 생각했습니다. 시작점을 기준으로 특정 점까지 가는 거리를 구하는 문제이기에, 다익스트라에서 로직을 살짝 바꿔주면 될 거라고 생각했습니다. 한 번 틀렸는데, min을 써야할 곳에 max를 쓰는 실수를 고치니 정답을 얻었습니다..

https://www.acmicpc.net/problem/17451 17451번: 평행 우주 행성 1에 가기 위해 필요한 것보다 세 배의 속도로, 행성 2의 경우 두 배의 속도로 이동하면, 지구에서는 900의 속도만 쌓으면 된다. www.acmicpc.net 풀이 1. 이분 탐색 지구에서 올리는 속도 v를 이분 탐색을 통해 최솟값을 찾는 풀이입니다. 최소 속도의 최댓값이 얼마나 될지 살짝 감이 안 잡히나, 9억이 넘는 서로 다른 세 소수 a, b, c (a (int의 max 범위) 이므로 int 범위를 벗어납니다. 따라서, 일단 long으로 찾아야 한다는 사실을 발견할 수 있습..

https://www.acmicpc.net/problem/1477 1477번: 휴게소 세우기 첫째 줄에 현재 휴게소의 개수 N, 더 지으려고 하는 휴게소의 개수 M, 고속도로의 길이 L이 주어진다. 둘째 줄에 현재 휴게소의 위치가 공백을 사이에 두고 주어진다. www.acmicpc.net 문제 다솜이는 유료 고속도로를 가지고 있다. 다솜이는 현재 고속도로에 휴게소를 N개 가지고 있는데, 휴게소의 위치는 고속도로의 시작으로부터 얼만큼 떨어져 있는지로 주어진다. 다솜이는 지금 휴게소를 M개 더 세우려고 한다. 다솜이는 이미 휴게소가 있는 곳에 휴게소를 또 세울 수 없고, 고속도로의 끝에도 휴게소를 세울 수 없다. 휴게소는 정수 위치에만 세울 수 있다. 다솜이는 이 고속도로를 이용할 때, 모든 휴게소를 방문한..