본문 바로가기

알고리즘60

[Python] 백준 2262번: 토너먼트 만들기 요약 어차피 마지막으로 남게되는 숫자는 1이기 때문에 제일 큰수부터 1이남을때까지 양쪽차중에 적은수를 더해주면 된다. INF = 2147000000 n = int(input()) toner = [INF] + list(map(int, input().split())) + [INF] ans = 0 while n >= 2: idx = toner.index(n) ans += min(abs(toner[idx] - toner[idx-1]), abs(toner[idx] - toner[idx+1])) del toner[idx] n -= 1 print(ans) 2021. 9. 14.
[Python] 백준 2879번: 코딩은 예쁘게 https://www.acmicpc.net/problem/2879 2879번: 코딩은 예쁘게 첫째 줄에 줄의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 현재 줄에 있는 탭의 개수가 주어지며, 1번째 줄부터 순서대로 주어진다. 탭의 개수는 0보다 크거나 같고, 80보다 작거나 같은 정수 www.acmicpc.net 1. 출발탭과 목표탭의 차를 구하고 양수와 음수의 그룹을 분리해준다. (양수와 음수의 분리를 위해, 양수와 음수를 같이연산하면 반대연산은 자꾸 늘어나기때문 ex) 1 -1 에 + 1 을하면 2 0 즉 음수는 사라졌지만 양수의 연산은 하나 더 늘었다) 2. 제일 작은수를 기준으로 분할해서 재귀를 돌려준다. ex) 3 2 1 2 3 (-1) > 2 1 0 1 2 0을 기준으로 분리.. 2021. 9. 14.
[Python] 백준 17619번: 개구리 점프 https://www.acmicpc.net/problem/17619 17619번: 개구리 점프 첫 번째 줄에 통나무 개수 N과 질문의 개수 Q가 주어진다. 다음 N개의 줄에 각 통나무에 x1, x2, y의 세 정수 좌표가 주어진다. 주어진 통나무는 두 점 (x1, y)와 (x2, y)를 잇는 형태이다. (x1 < x2) 모든 www.acmicpc.net 1. 통나무의 높이는 크게 상관이없다. 통나무끼리의 길이만 겹쳐있으면 어디로든지 이동할수있다. 2. 처음에 x길이를 기준으로 정렬을 해준다. 3. union & find로 길이가 겹치면 이전노드로 현재노드를 묶어주고 ny길이값을 갱신해준다(처음에 정렬했기때문에 x값은 고정). 4. 길이가 겹치지않으면 nx, ny 값을 다음 x, y 값으로 초기화해준다. .. 2021. 9. 14.
[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, 0≤A[i]≤1,000,000,000 이며 모든 입력은 정수이다. www.acmicpc.net 처음 마을을 기준으로 나머지 마을까지의 인원의 총 거리의 합을 저장한다. 그리고 지나온 마을의 인원수를 lt에 저장하고 나머지 마을의 인원을 rt에 저장한다. 이동한거리(dif) 만큼 지나온 마을은 더해주고 나머지 마을을 빼준다. 2021. 9. 14.