본문 바로가기
728x90

알고리즘316

[python] 백준 13904 과제 https://www.acmicpc.net/problem/13904 13904번: 과제 예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다. www.acmicpc.net 문제 해결 어떻게 일을 먼저 계획할 것인지 순서를 정하는 문제 당연히 점수가 높은 일을 먼저 계획을 해야한다.(중요하기 때문) 그다음 고려할 것은 가능하면 빨리 해결해야하는 문제이다. 따라서 힙(heap)을 사용할 것이다. 그리고 가능하면 마감기간에 처리를 하여 비록 비중이 적지만 빨리 처리해야하는 것도 처리할 수 있도록 한다. CODE import sys input = sys.stdin.readline import heapq def sol.. 2023. 12. 14.
[python] 백준 10835 카드게임 https://www.acmicpc.net/problem/10835 10835번: 카드게임 첫 줄에는 한 더미의 카드의 개수를 나타내는 자연수 N(1 ≤ N ≤ 2,000)이 주어진다. 다음 줄에는 왼쪽 더미의 카드에 적힌 정수 A(1 ≤ A ≤ 2,000)가 카드 순서대로 N개 주어진다. 그 다음 줄에는 오 www.acmicpc.net 문제 해결 사실 처음에 DFS를 이용해서 완전탐색을 하면 쉽게 풀 수 있겠다 싶었다. 하지만 DFS의 시간복잡도는 $O(2^{N})$ 이며 1≤$N$≤2,000이기 때문에 매우 복잡해질 수 있었고 시간초과로 부분점수밖에 얻지 못했다. 사실 숫자가 크고 완전탐색이 필요한 경우는 대부분 DP로 푸는 경우였다. 우선 왼쪽 카드 중 가장 큰 수가 오른쪽 카드 중 가장 큰 수보다.. 2023. 12. 13.
[python] 백준 13335 트럭 https://www.acmicpc.net/problem/13335 13335번: 트럭 입력 데이터는 표준입력을 사용한다. 입력은 두 줄로 이루어진다. 입력의 첫 번째 줄에는 세 개의 정수 n (1 ≤ n ≤ 1,000) , w (1 ≤ w ≤ 100) and L (10 ≤ L ≤ 1,000)이 주어지는데, n은 다리를 건너는 트 www.acmicpc.net 문제 해결 다리를 que를 이용하여 해결하면 좋겠다는 생각이 바로 든다. que안에 있는 숫자의 합은 l을 넘어서는 안된다. 1초마다 FIFO로 첫 번째 트럭 or 공기(?)가 나가고 대기중인 트럭이 들어오거나 공기가 들어오는 시물레이션을 코딩하면 된다. 공기가 들어갈지 트럭이 들어갈지의 기준은 다리에 있는 무게의 합+대기중인 트럭의 무게가 l보다 .. 2023. 12. 10.
[python] 백준 1069 집으로 https://www.acmicpc.net/problem/1069 1069번: 집으로 은진이는 지금 (X, Y)에 있고, (0, 0)에 있는 집으로 가능한 빨리 가려고 한다. 이동할 수 있는 방법은 다음 두 가지이다. 첫 번째 방법은 걷는것이다. 걸을 때는 1초에 1만큼 움직인다. 두 번째 방법 www.acmicpc.net 문제 해결 걸을 때 1초에 1만큼 움직인다. 이는 택시기하학으로 움직이는 것이 아니고 자유롭게 대각선이든 반경 1안에 모든 점으로 1초에 이동할 수 있다는 것이다. 점프도 마찬가지다. 일직선으로 할 수 있다는 뜻은 정확히 거리가 D인 지점까지 T초에 간다는 뜻이다. 따라서 현재 거리, 즉 (x,y)와 (0,0) 거리를 구한다. 현재 거리가 한 번에 뛰어서 갈 수 있는 거리보다 크거나 .. 2023. 12. 7.
728x90