Algorithm475 [파이썬] 백준 1633 : 최고의 팀 만들기 (골드4) [파이썬] 백준 1633 : 최고의 팀 만들기 (골드4)https://www.acmicpc.net/problem/1633풀이방향성 생각state가 어떻게 결정되는지 생각한다.N>30인 경우에는 안뽑히는 사람도 존재한다.k명을 뽑았을 때, 흑팀의 수 b, 백팀의 수 w로 상태가 나뉜다.접근은 remain black, remain white, choose k로 시작했다.DFS를 통해서 뽑아야 하는 B와 W의 숫자,현재 탐색중인 사람 idx를 넘겨줬다.전체코드from collections import defaultdict as ddarr = []while True: try: arr.append(tuple(map(int,input().split()))) except: brea.. 2024. 10. 1. [파이썬] 백준 1368 : 물대기 (골드2) [파이썬] 백준 1368 : 물대기 (골드2)https://www.acmicpc.net/problem/1368문제[문제]선주는 자신이 운영하는 N개의 논에 물을 대려고 한다.물을 대는 방법은 두 가지가 있다.1. 하나는 직접 논에 우물을 파는 것이고 2. 다른 하나는 이미 물을 대고 있는 다른 논으로부터 물을 끌어오는 법이다.각각의 논에 대해 우물을 파는 비용과 논들 사이에 물을 끌어오는 비용들이 주어졌을 때, 최소의 비용으로 모든 논에 물을 대는 것이 문제이다.[입력]첫 줄에는 논의 수 N(1 ≤ N ≤ 300)이 주어진다.다음 N개의 줄에는 i번째 논에 우물을 팔 때 드는 비용 Wi(1 ≤ Wi ≤ 100,000)가 순서대로 들어온다.다음 N개의 줄에 대해서는 각 줄에 N개의 수가 들어온다.이는 i번.. 2024. 9. 21. [파이썬] 백준 1197 : 최소 스패닝 트리 (골드4) [파이썬] 백준 1197 : 최소 스패닝 트리 (골드4)https://www.acmicpc.net/problem/1197풀이방향성 생각유니온 파인드로 구현.시간 줄이고 싶으면 모든 노드가 연결되면 탈출하는 방식으로 풀이.루프 방지를 위해서 항상 번호가 작은 노드를 루트로 한다.이 문제의 경우에는 그냥 넘어가지만, 모든 노드가 어떻게 연결되었는지 확인을 해야하는 경우에는 각 노드마다 find(node)로 경로압축을 꼭 해주자.전체코드import syssys.setrecursionlimit(10**6) input = lambda : sys.stdin.readline().rstrip()V,E = map(int,input().split())G = [list(map(int,input().split())) for .. 2024. 9. 3. [파이썬] 백준 10942 : 팰린드롬? (골드4) [파이썬] 백준 10942 : 팰린드롬? (골드4)https://www.acmicpc.net/problem/10942풀이방향성 생각전형적인 DP각 쿼리마다 체크하거나, $N^2$로 체크하면 시간초과한다.시간 제한이 0.5초이고 쿼리 개수가 많아서 DP 리스트에 접근하면 시간초과.DP를 통해서 순회를 줄인 후, 쿼리를 결과를 출력한다.전체코드import sysinput = lambda : sys.stdin.readline().rstrip()N = int(input())arr = list(map(int,input().split()))dp = [[0]*(N) for _ in range(N)] #dp[시작idx][끝idx]# 길이 1은 팰린드롬for i in range(N): dp[i][i] = 1# 길이.. 2024. 8. 4. 이전 1 ··· 39 40 41 42 43 44 45 ··· 119 다음