본문 바로가기
728x90

알고리즘316

[python] 백준 2141 우체국 https://www.acmicpc.net/problem/2141 2141번: 우체국 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 X[1], A[1], X[2], A[2], …, X[N], A[N]이 주어진다. 범위는 |X[i]| ≤ 1,000,000,000, 1 ≤ A[i] ≤ 1,000,000,000 이며 모든 입력은 정수이다. www.acmicpc.net 문제 해결 $ L_{1} $ 공간에서 $ \sum_{i=1}^{n} |x_{i}-a| \times b $ 의 최솟값은 표본의 중앙값이 위치한 값이라는 것을 이용하는 문제이다. https://math.stackexchange.com/questions/4410205/minimum-value-of-sum-of-absolu.. 2023. 4. 9.
[python] 백준 1238 파티 https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 문제 해결 다익스트라 문제 for문을 통해 1~n까지 한 점 i에서 x까지 가는데 최소 시간를 구하고 x에서 i까지 가는데 최소 시간를 구해서 더하면 왕복 최소 시간이 나온다. 리스트를 통해 최댓값을 구하면 된다. CODE import sys input = sys.stdin.readline import heapq INF = sys.maxsize n, m, x = ma.. 2023. 4. 9.
[python] 백준 2660 회장뽑기 https://www.acmicpc.net/problem/2660 2660번: 회장뽑기 입력의 첫째 줄에는 회원의 수가 있다. 단, 회원의 수는 50명을 넘지 않는다. 둘째 줄 이후로는 한 줄에 두 개의 회원번호가 있는데, 이것은 두 회원이 서로 친구임을 나타낸다. 회원번호는 1부터 www.acmicpc.net 문제 해결 전형적인 플로이드-위셜 문제 CODE import sys input = sys.stdin.readline INF = sys.maxsize n = int(input().rstrip()) dp = [[INF]*(n+1) for _ in range(n+1)] while True: a, b = map(int, input().split()) if a==-1 and b == -1 : break d.. 2023. 4. 9.
[python] 백준 7570 줄 세우기 https://www.acmicpc.net/problem/7570 7570번: 줄 세우기 입력은 2 개의 줄로 이루어져 있다. 첫 줄에는 어린이 수를 나타내는 정수가 주어진다. 둘째 줄에는 처음에 줄서있는 어린이들의 번호가 차례대로 주어진다. 주어진 번호들 사이에는 공백이 하 www.acmicpc.net 문제 해결 임의의 배열을 최소한의 이동을 통해 [i for i in range(n+1)] 를 만들면 된다. 이 말은 원소가 계속 증가 수열이 되도록 하면 된다는 것과 동치이다. (원소가 1~n까지 고정이므로) 이 문제를 보자마자 최대로 긴 증가 수열을 구하는 문제를 떠올렸다. 증가하다 끊긴 부분에서 두 원소 중 하나는 무조건 이동을 해야한다. 그리고 다시 증가하는 수열이 생겨도 원소 시이에 원소를 넣을 .. 2023. 4. 8.
728x90