본문 바로가기

분류 전체보기282

2473. 세 용액 (Python) 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 풀이 두 용액(링크)과 유사한 문제로 투 포인터를 사용하여 문제를 해결할 수 있다. 문제는 총 3개의 용액을 더해야 한다는 것인데 3개의 포인터를 두고 탐색하되 하나의 포인터는 움직이지 않고 고정시킨다. 그리고 나머지 2개의 포인터를 기존의 두 용액에서와 마찬가지로 합이 양수냐 음수냐에 따라서 이동시켜가며 0에 가까운 세 용액을 구하면 된다. 코드 if __name__ == '__main__': N = int(input()) values =.. 2022. 6. 19.
2629. 양팔저울 (Python) 2629번: 양팔저울 첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30 이하이다. 둘째 줄에는 추의 무게들이 자연수로 가벼운 것부터 차례로 주어진다. 같은 무게의 추가 여러 개 있을 수도 있다. 추의 무 www.acmicpc.net 풀이 재귀를 사용하여 1)저울의 왼쪽에 추를 올리는 경우, 2)저울의 오른쪽에 추를 올리는 경우, 3)추를 저울에 올리지 않는 경우로 나누어 재귀를 통해 구할 수 있는 구슬의 무게에 대한 경우의 수를 체크한다. 2차원 배열 dp에는 다음과 같은 정보가 저장된다. dp[weight][n] -> n번 추까지 사용했을 때 무게 weight를 만들 수 있는지에 대한 정보 코드 from collections import defaultdict # idx: idx번 째 추, .. 2022. 6. 18.
13905. 세부 (Python) 13905번: 세부 첫 번째 줄에는 섬에 존재하는 집의 수 N(2≤N≤100,000)와 다리의 수 M(1≤M≤300,000)이 주어진다. 두 번째 줄에는 숭이의 출발 위치(s)와 혜빈이의 위치(e)가 주어진다. (1≤s, e≤N, s≠e). 다음 M개의 줄 www.acmicpc.net 풀이 모든 경로를 탐색해가면서 최대 개수를 구하면 시간초과가 발생한다. 따라서 처음부터 모든 경로를 탐색하는 것이 아니라 임의의 개수 k개를 혜빈이의 위치까지 들고갈 수 있는 경로가 있는지를 탐색하면 된다. 임의의 개수 k개는 이분 탐색을 사용하여 정할 수 있다. 즉, 이분 탐색과 BFS를 사용하여 문제를 해결하면 된다. 코드 import sys from collections import deque input = sys.s.. 2022. 6. 17.
2251. 물통 (Python) 2251번: 물통 각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부 www.acmicpc.net 풀이 BFS를 통해서 from 물통에서 to 물통으로 물을 쏟아 부은 후 A 물통과 C 물통의 물의 양을 살펴본다. 큐에는 리스트의 형태로 '[A 물통의 물의 양, B 물통의 물의 양, C 물통의 물의 양]'으로 값을 넣어 줬다. 큐에 중복된 경우를 넣지 않게 하기 위해 물의 양들을 문자열로 만들고 이를 딕셔너리의 키로 사용하여 체크해줬다. 예를 들어 A, B, C에 각각 4, 3, 22 리터의 물이 들어있다면 문자열로 '4 3 22'와 같이.. 2022. 6. 16.
17612. 쇼핑몰 (Python) 17612번: 쇼핑몰 입력의 첫 줄에는 2개의 정수 N(1 ≤ N ≤ 100,000)과 k(1 ≤ k ≤ 100,000)가 주어진다. 다음 줄부터 N개의 줄에 걸쳐 고객 N명의 정보가 줄 맨 앞의 고객부터 맨 뒤 고객까지 순서대로 주어진다. i번째 www.acmicpc.net 풀이 고객이 계산대에 들어갈 때와 나갈 때, 두 경우에 대해서 최소 힙을 사용한다. 먼저 계산을 하러 들어갈 때는 최소 힙에 (시간, 계산대, 고객 번호)와 같은 형태로 넣어줬다. 만약 같은 시간에 계산대가 비는 경우 번호가 작은 계산대에 현재 손님이 배정된다. 계산을 마치고 나가는 최소 힙에는 (시간, -계산대, 고객 번호)와 같은 형태로 값을 넣어줬다. 만약 같은 시간에 계산을 마쳤을 경우에는 출구에 가까운 높은 번호 계산대의 .. 2022. 6. 14.
17616. 등수 찾기 (Python) 17616번: 등수 찾기 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에 세 정수 N, M, X가 공백을 사이에 두고 주어진다. (2 ≤ N ≤ 105, 1 ≤ M ≤ min(N(N-1)/2, 5×105), 1 ≤ X ≤ N) . 다음 M 줄에는 각각 두 정수 A, B가 주어 www.acmicpc.net 풀이 두 개의 리스트를 사용하여 그래프를 저장하고 두 번의 DFS를 통해서 문제를 해결할 수 있다. 두 개의 리스트는 각각 자신보다 등수가 높은 학생들의 번호와 자신보다 등수가 낮은 학생들의 번호를 저장한다. 입력에서 주어지는 X번 학생부터 시작하여 DFS를 통해 자신보다 등수가 높은 학생이 총 몇 명있는지를 체크하고 다시 한 번 DFS를 통해 자신보다 등수가 낮은 학생이 총 몇 명 있는지를 체크한 .. 2022. 6. 13.

티스토리툴바