Python43 [백준] LCA https://www.acmicpc.net/problem/11437 11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 문제 제목 그대로 LCA 문제입니다. 일반적인 DFS로는 시간초과가 발생할 것 같아서 DP와 결합된 LCA알고리즘을 활용하여 풀이하였습니다. import sys from collections import defaultdict from math import log, ceil sys.setrecursionlimit(10 ** 6) # sys.stdin = open("input.txt", "r").. 2023. 2. 21. [백준] 당근 훔쳐 먹기 https://www.acmicpc.net/problem/18234 18234번: 당근 훔쳐 먹기 첫 번째 줄에 N(1 ≤ N ≤ 200,000)과 T(N ≤ T ≤ 100,000,000)가 공백으로 구분되어 주어진다. 오리는 당근의 맛을 충분히 높이기 위해 항상 N이상인 T일 동안 재배한다. 다음 N개의 줄에 걸쳐서 i+1번째 www.acmicpc.net 간단한 정렬문제입니다. 당근들은 매일 pi만큼 맛이 증가하고 시작인 wi가 pi보다 항상 작거나 같기 때문에 pi가 큰 순으로 내림차순 정렬한 다음 t일, t - 1일, t - 2일.. 에 하나씩 먹어주면 가장 최대의 맛을 얻을 수 있습니다. import sys # sys.stdin = open("input.txt", "r") input = sys.s.. 2023. 2. 20. [백준] 정복자 https://www.acmicpc.net/problem/14950 14950번: 정복자 서강 나라는 N개의 도시와 M개의 도로로 이루어졌다. 모든 도시의 쌍에는 그 도시를 연결하는 도로로 구성된 경로가 있다. 각 도로는 양방향 도로이며, 각 도로는 사용하는데 필요한 비용이 존재 www.acmicpc.net MST를 구하는 문제입니다. 프림, 크루스칼로 MST를 구한 다음 증가하는 비용만큼을 추가해주면 됩니다. N개의 노드에서 MST를 선택하면 N - 1개의 간선을 선택하게 되고 증가하는 비용의 총합은 0 ~ N - 2의 합 * t이므로 MST의 간선의 합에 추가적으로 더해주면 됩니다. 프림 import sys, heapq from collections import defaultdict # sys.std.. 2023. 2. 19. [백준] 같이 눈사람 만들래? https://www.acmicpc.net/problem/20366 20366번: 같이 눈사람 만들래? 높이가 (2, 5), (3, 5)로 구성된 눈사람 둘을 만드는 것이 최적의 경우 중 하나이다. |7-8| = 1 다른 경우로는 (2, 9), (5, 5)로 두 눈사람을 만드는 경우가 있다. |11-10| = 1 www.acmicpc.net 4개의 수중 2개씩 수를 더한 다음 합쳐진 2개의 수의 차이가 적게 되도록 해야합니다. 차이가 작아지려면 2개의 수를 합칠 때에 반드시 (가장 큰 수 + 가장 작은 수), (2번째로 큰 수 + 3번재로 큰 수)가 되어야한다는 점을 활용하여 풀이하였습니다. 눈덩이를 오름차순으로 정렬한 다음 가장 작은 수와 가장 큰 수를 각각 i, j가 가르키도록 합니다. 그리고 해당 .. 2023. 2. 18. [백준] 🎵니가 싫어 싫어 너무 싫어 싫어 오지 마 내게 찝쩍대지마🎵 - 1 https://www.acmicpc.net/problem/20440 20440번: 🎵니가 싫어 싫어 너무 싫어 싫어 오지 마 내게 찝쩍대지마🎵 - 1 첫째 줄에 지동이의 방에 출입한 모기의 마릿수 N(1 ≤ N ≤ 1,000,000)가 주어진다. 다음 N개의 줄에 모기의 입장 시각 TE과 퇴장 시각 TX이 주어진다. (0 ≤ TE ans: ans_start = t ans = cnt + time[t] isUpdated = True # 답이 갱신된 적이 있고 값이 더 적어진다면 최장 기간이 끝난 것이므로 기록해준다. if isUpdated and cnt + time[t] < ans: ans_end = t isUpdated = False cnt += time[t] print(ans) print(ans_star.. 2023. 2. 17. [백준] 계보 복원가 호석 https://www.acmicpc.net/problem/21276 21276번: 계보 복원가 호석 석호촌에는 N 명의 사람이 살고 있다. 굉장히 활발한 성격인 석호촌 사람들은 옆 집 상도 아버님, 뒷집 하은 할머님 , 강 건너 유리 어머님 등 모두가 한 가족처럼 살아가고 있다. 그러던 어느 날 www.acmicpc.net 어제에 이어서 오늘도 호석님에게 고통받을 뻔 했으나 오늘은 잘 넘겼습니다. 위상 정렬을 사용하여 풀 수 있는 문제입니다. 각 가문의 시조를 찾아서 시조를 시작으로 위상정렬을 수행해주면 됩니다. indegree를 0으로 만드는 조상이 바로 부모이므로 indegree를 0으로 만드는 부모의 자식으로 저장해주면 풀 수 있습니다. import sys from collections import.. 2023. 2. 15. [백준] 장난감 조립 https://www.acmicpc.net/problem/2637 2637번: 장난감 조립 첫째 줄에는 자연수 N(3 ≤ N ≤ 100)이 주어지는데, 1부터 N-1까지는 기본 부품이나 중간 부품의 번호를 나타내고, N은 완제품의 번호를 나타낸다. 그리고 그 다음 줄에는 자연수 M(3 ≤ M ≤ 100)이 주 www.acmicpc.net 위상정렬과 DP를 함께 수행하는 문제입니다. 골드 2문제라서 그런지 난이도가 꽤 있었습니다. 단순히 위상정렬만 실행을 하면 메모리 초과가 떠서 DP까지 함께 수행을 해줘야합니다. 먼저 기초 부품들을 따로 저장해두고 각 부품별 필요한 기초 부품들을 dp 배열에 저장해둡니다. dp[i][j]는 j를 만들기 위한 i번째 기초 부품의 개수를 저장하고 있습니다. 위상정렬을 해주면.. 2023. 2. 14. [백준] 문자열 생성 https://www.acmicpc.net/problem/6137 6137번: 문자열 생성 첫 번째 줄에 문자열 S의 길이 N이 주어진다. (N = right: answer += dq.popleft() else: answer += dq.pop() if len(answer) == 80: print(answer) answer = "" cnt += 1 if answer: print(answer, end="") 2023. 2. 14. [백준] Coins https://www.acmicpc.net/problem/3067 3067번: Coins 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 모든 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어 30원을 만들기 위해 www.acmicpc.net 냅색문제입니다. dp[i][j]를 i번째 동전을 사용하지 않고 j원을 만들 수 있는 경우와 i번째 동전을 사용하여 j원을 만들 수 있는 경우 두가지로 나누어서 생각하면 풀이할 수 있습니다. import sys # sys.stdin = open("input.txt", "r") input = sys.stdin.readline T = int(input()) for _ in rang.. 2023. 2. 13. 이전 1 2 3 4 5 다음
