본문 바로가기

Algorithm475

[파이썬] 백준 7453 : 합이 0인 네 정수 (골드2) [파이썬] 백준 7453 : 합이 0인 네 정수 (골드2) https://www.acmicpc.net/problem/7453 풀이 방향성 생각 투포인터 태그가 있긴한데 해싱이 조금 더 직관적인 풀이라고 생각한다. AB에서 N^2, CD 에서 N^2의 모든 경우의 수를 만든다. AB에 저장된 숫자로 CD에 매칭되는 숫자는 유일하니 이 경우를 카운팅하기 전체코드 from collections import defaultdict as dd import sys input = lambda : sys.stdin.readline().rstrip() N = int(input()) A,B,C,D = [],[],[],[] for _ in range(N): a,b,c,d = map(int,input().split()) A.a.. 2024. 4. 22.
[파이썬] 백준 10986 : 나머지 합 (골드3) [파이썬] 백준 10986 : 나머지 합 (골드3) https://www.acmicpc.net/problem/10986 풀이 방향성 생각 이제까지 등장한 누적합%M과 같을 경우, 매칭이 가능하다. 순회를 한 번 하면서 누적합에 기록된 숫자들을 딕셔너리에 기록한다. 누적합에 기록된 숫자 자체가 M으로 나누어 떨어지면, 혼자 만으로 정답 체크가 된다. M으로 나누어 떨어지는 경우에는 KC2 + K, 아닌 경우에는 KC2를 카운팅한다. 전체코드 # %% from collections import defaultdict as dd N,M = map(int,input().split()) arr = list(map(int,input().split())) S = [arr[0]%M] for v in arr[1:]: S... 2024. 4. 21.
[파이썬] 백준 3109 : 빵집 (골드2) [파이썬] 백준 3109: 빵집 (골드2) https://www.acmicpc.net/problem/3109 풀이 방향성 생각 왼쪽 위에서 탐색을 시작한다고 하면, 파이프를 최대한 오른쪽 아래에서 멀어지게 설치해야함. 파이프를 겹쳐서 놓을 수 없기 때문에, 다른 파이프를 막을 수 있기 때문 위쪽에서 탐색을 시작해서 최대한 파이프를 위에다 갖다놓자. 탐색 도중에 끝까지 도달하지 못하면, 다른 경로를 통해서 그 지점에 도달했을 경우에도 도달하지 못한다. 탐색하면서 arr를 바꿔준다. 백트래킹처럼 원상태로 돌릴 필요는 없다. 전체코드 import sys input = lambda : sys.stdin.readline().rstrip() H,W = map(int,input().split()) arr = [lis.. 2024. 4. 14.
[파이썬] 백준 6497 : 전력난 (골드4) [파이썬] 백준 6497 : 전력난 (골드4) https://www.acmicpc.net/problem/6497 풀이 방향성 생각 MST를 만들어서 필요없는 간선의 cost가 얼마인지 구하자. 전체코드 import sys input = lambda : sys.stdin.readline().rstrip() def find(a): if parent[a] != a: parent[a] = find(parent[a]) return parent[a] def union(a,b): parent[max(a,b)] = min(a,b) while True: # TEST CASE : 입력 -> 간선 N,K = map(int,input().split()) if (N,K) == (0,0): break # edges를 내림차순으로.. 2024. 4. 13.

티스토리툴바