본문 바로가기

파이썬

 (320)
[Python] 23740번 버스 노선 개편하기 https://www.acmicpc.net/problem/23740 23740번: 버스 노선 개편하기 서강 나라에서는 일직선 도로를 따라 $N$개의 버스 노선을 운영 중이다. 필요할 때마다 노선을 새로 만든 탓에 겹치거나 중복되는 노선이 많다. 복잡한 버스 노선에 지친 시민들을 위해 버스 노 www.acmicpc.net 23/09/02 스위핑 기초를 다질 수 있는 문제로, 2170번 선 긋기 문제의 응용 버전 문제라고 생각할 수 있다. 문제 접근 방식: 문제 접근 방식은 다음과 같다. 1. $N$개의 입력 $S, E, C$를 $S$를 중심으로 내림차순 정렬한다. 2. 이후 리스트에서 마지막 원소(시작 지점이 가장 작은 버스)를 뽑아 새로 만드는 버스 노선의 시작 지점, 도착 지점, 비용($\textrm{..
[Python] 1092번 배 https://www.acmicpc.net/problem/1092 1092번: 배 첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보 www.acmicpc.net 23/09/03 그리디적으로 접근하면 풀리는 문제로, 구현이 살짝 까다로웠다. 문제 접근 방식: 생각한 방법은 다음과 같았다. 1. 크레인과 박스가 있으면 두 리스트를 모두 내림차순 정렬한다. 2. 만약 가장 무거운 박스와 가장 무거운 무게를 들 수 있는 크레인의 무게제한을 비교했을 때, 가장 무거운 박스가 더 무겁다면 어떻게 하더라도 그 박스는 옮길 수 없으므로, $-1$을 출력..
[Python] 13249번 공의 충돌 https://www.acmicpc.net/problem/13249 13249번: 공의 충돌 무게가 모두 같고, 크기가 0인 공 N개가 일직선 위에 놓여져 있다. 오른쪽으로 굴러가는 공과 왼쪽으로 굴러가는 공이 같은 속도로 충돌하면, 속도는 변하지 않고 공의 진행 방향만 바뀌게 된다. www.acmicpc.net 23/08/24 매우 유명한 애드혹 문제에 기댓값을 섞은 문제로, 아이디어만 알면 쉽게 구현할 수 있는 문제이다. 첫 번째 접근 방식: 먼저, 이 문제의 아이디어의 원천이 되는 한 문제를 보자. https://www.acmicpc.net/problem/4307 4307번: 개미 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 막대의 길이와 개미의 수 n이 주어진다. ..
[Python] 18689번 Baklawa https://www.acmicpc.net/problem/18689 18689번: Baklawa Baklawa or baklava, is a sweet middle eastern dessert, mainly made from phyllo dough sheets, walnuts, and sugar syrup cut into small cubic pieces and served in cuboid boxes containing multiple layers. Alice and Bob love to play what they call the last Bakl www.acmicpc.net 23/08/19 전형적인 스프라그-그런디 문제로, 문제의 상황을 님게임으로 변형시키기만 하면 해결할 수 있는 매우 쉬운 문제이다..
[Python] 26074번 곰곰이와 테트리스 https://www.acmicpc.net/problem/26074 26074번: 곰곰이와 테트리스 곰곰이가 첫 차례에 4번째 종류의 블록(2×2 모양)을 그림과 같이 배치하고 20점을 획득하면, 이후 게임이 어떻게 흘러가던 관련 없이 무조건 이길 수 있다. www.acmicpc.net 23/08/24 이전에 곰곰컵 때 이 문제를 풀어보려고 시도했다가 실패했었다. 엄청난 전략이 숨어있는 문제로, 이 글을 보기 전에 충분한 고민을 하기 추천한다. 여담으로 내 1800번째 문제이다. 문제 접근 방식: 이 문제는 겉으로 볼 때 많은 것들을 고려해야 되는 것처럼 보인다. 블록 별로 점수가 다양하게 주어지고, 판의 크기 또한 다양하게 주어지는 상황 속에서 "최적의 행동"을 생각해야 하기 때문이다. 이 문제의 핵심..
[Python] 6068번 시간 관리하기 / 1263번 시간 관리 / 7983번 내일 할거야 https://www.acmicpc.net/problem/6068 6068번: 시간 관리하기 성실한 농부 존은 시간을 효율적으로 관리해야 한다는 걸 깨달았다. 그는 N개의 해야할 일에 (1
[Python] 13255번 동전 뒤집기 https://www.acmicpc.net/problem/13255 13255번: 동전 뒤집기 첫째 줄에 동전의 개수 N (1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 K (1 ≤ K ≤ 50)이 주어진다. 셋째 줄에는 A[i] (1 ≤ A[i] ≤ N)가 주어진다. www.acmicpc.net 23/08/23 최근 확률 DP 문제를 계속 공부하고 있다. 이 문제 또한 확률 DP 문제로 쉽게 해결할 수 있다. 또한, 약간의 최적화를 거치면 매우 빠르게 문제를 해결할 수 있다. 첫번째 접근 방식: 첫 번째로 접근한 방식은 나이브한 $3$차원 확률 DP이다. DP테이블은 다음과 같이 정의했다. $$DP[i][j][k] = i번째 \ 뒤집는 \ 행위를 \ 수행했을 \ 때 \ j번째 \ 동전이 \ k번 ..
[Python] 12046번 Not So Random (Small) / 12047번 Not So Random (Large) https://www.acmicpc.net/problem/12046 12046번: Not So Random (Small) The first line of the input gives the number of test cases, T. T test cases follow; each consists of one line with six integers N, X, K, A, B, and C. Respectively, these denote the number of machines, the initial input, the fixed number with which www.acmicpc.net https://www.acmicpc.net/problem/12047 12047번: Not So Random (Large..

티스토리툴바