본문 바로가기

전체 글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.
4811. 알약 (Python) 4811번: 알약 입력은 최대 1000개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄이며, 병에 들어있는 약의 개수 N ≤ 30 가 주어진다. 입력의 마지막 줄에는 0이 하나 주어진다. www.acmicpc.net 풀이 재귀를 통해서 경우의 수를 구할 수 있고, 2차원 dp는 다음과 같은 정보를 갖는다. dp[w][h] : W가 w개 있고 H가 h개 있을 때 만들 수 있는 문자의 수 재귀 함수는 다음과 같이 정의되어 있다. solve(w, h) -> w: 현재 갖고 있는 W의 개수, h: 현재 갖고 있는 H의 개수 처음 재귀 함수의 호출은 solve(N-1, 1)과 같은 형태를 갖는다(N은 알약의 개수). 처음에는 온전한 형태의 약만 존재하기 때문에 문자열의 첫 번째 문자는 무조건 W가 .. 2022. 6. 13.
2624. 동전 바꿔주기 (Python) 2624번: 동전 바꿔주기 명보네 동네 가게의 현금 출납기에는 k 가지 동전이 각각 n1, n2, … , nk개 씩 들어있다. 가게 주인은 명보에게 T원의 지폐를 동전으로 바꿔 주려고 한다. 이때, 동전 교환 방법은 여러 가지가 있을 www.acmicpc.net 풀이 1차원 dp를 사용하는데 dp 배열의 의미는 다음과 같다. dp[n] : 금액 n의 동전 교환 방법 경우의 수 모든 dp 배열의 값은 0으로 초기화 되지만 dp[0]은 아무 동전도 사용하지 않는 경우 하나가 존재한다고 가정하여 dp[0]은 1로 초기화한다. 경우의 수를 구하기 위한 점화식은 다음과 같다. dp[money] += dp[money - coin * cnt] (money는 구하기 위한 금액, coin은 현재 사용하는 동전의 금액,.. 2022. 6. 11.
1774. 우주신과의 교감 (Python) 1774번: 우주신과의 교감 (1,1) (3,1) (2,3) (4,3) 이렇게 우주신들과 황선자씨의 좌표가 주어졌고 1번하고 4번이 연결되어 있다. 그렇다면 1번하고 2번을 잇는 통로를 만들고 3번하고 4번을 잇는 통로를 만들면 신들과 선자씨끼 www.acmicpc.net 풀이 최소 신장 트리(MST)를 이용하여 해결하는 문제이다. MST를 만드는 방법에는 크루스칼 알고리즘과 프림 알고리즘이 있다. 자세한건 검색을 통해 알아보자. 간단하게 설명하면 다음과 같다. * 크루스칼 알고리즘 : 모든 간선을 길이에 따라 오름차순으로 정렬하여 크기가 작은 간선부터 사용한다. 간선을 사용했을 때 사이클이 발생하지 않는지를 체크한다. * 프림 알고리즘 : 시작 정점을 기준으로 선택할 수 있는 간선 중 가장 크기가 작은.. 2022. 6. 10.

티스토리툴바