본문 바로가기

분류 전체보기

(402)
[백준 9466번] 텀 프로젝트 (Python3) import sys input = sys.stdin.readline def BFS(n): now = n while True: next = pick[now-1] if visited[now] != 0 and visited[now] != n: break if visited[now] == n: if team[now] == 1: break else: team[now] = 1 now = next continue visited[now] = n if team[next] == 1: break now = next T = int(input()) for test in range(T): N = int(input()) pick = list(map(int,input().split())) visited = [0]*(N+1) team..
[백준 1007번] 벡터 매칭 (Python3) import sys input = sys.stdin.readline from itertools import combinations import math INF = 10**9 T = int(input()) for test in range(T): N = int(input()) xlist = [] ylist = [] for i in range(N): x,y = map(int,input().split()) xlist.append(x) ylist.append(y) xsum = sum(xlist) ysum = sum(ylist) result = INF for select in combinations(range(N),N//2): xsum1 = xsum ysum1 = ysum for i in select: xsum1 ..
[백준 16946번] 벽 부수고 이동하기 4 (Python3) import sys input = sys.stdin.readline from collections import deque dy = [1,-1,0,0] dx = [0,0,1,-1] N,M = map(int,input().split()) MAP = [] for i in range(N): MAP.append(list(map(int,list(input().strip())))) wall = [] for i in range(N): #벽 좌표 찾기 for j in range(M): if MAP[i][j] == 1: wall.append((i,j)) cntlist = {} def BFS(y,x,num): dq = deque() dq.append((y,x)) cnt = 0 while dq: y,x = dq.popleft..
[백준 16724번] 피리 부는 사나이 (Python3) import sys input = sys.stdin.readline N,M = map(int,input().split()) MAP = [] direction = {"U":[-1,0],"D":[1,0],"R":[0,1],"L":[0,-1]} parent = {(i,j):(i,j) for i in range(N) for j in range(M)} def findparent(tuple): if parent[tuple] == tuple: return tuple else: parent[tuple] = findparent(parent[tuple]) return parent[tuple] for i in range(N): MAP.append(input().strip()) for i in range(N): for j i..
[백준 20040번] 사이클 게임 (Python3) 여러가지로 힘들었고 배운점도 많았던 문제이다. 처음에는 엄청 간단한 문제라고 생각했다. "같은 집합에 속하면 cycle, 아니면 집합을 묶어주면 되잖아?" 라고 생각해서 모든 n에 대해 set()를 생성하고 연결될때마다 합쳐주는 방식을 생각했다. 코드는 아래와 같다. import sys input = sys.stdin.readline N,M = map(int,input().split()) setdict = {} for i in range(N): setdict[i] = {i} finish = False result = 0 for t in range(1,M+1): x,y = map(int,input().split()) if finish: continue if x in setdict[y]: finish = T..
[백준 7579번] 앱 (Python3) import sys input = sys.stdin.readline INF = 10**9 N,M = map(int,input().split()) memory = list(map(int,input().split())) cost = list(map(int,input().split())) sumcost = sum(cost) DP = [[0]*(sumcost+1) for i in range(N+1)] result = sumcost for n in range(1,N+1): for c in range(1,sumcost+1): m1 = memory[n-1] c1 = cost[n-1] DP[n][c] = DP[n-1][c] if c-c1 >= 0: DP[n][c] = max(DP[n][c],DP[n-1][c-c1]+m..
[백준 2473번] 세 용액 (Python3) import sys input = sys.stdin.readline INF = sys.maxsize N = int(input()) sol = sorted(list(map(int,input().split()))) result = [INF,False] for std in range(N-2): start = std+1 end = N-1 while True: if start == end: break SUM = sol[std] + sol[start] + sol[end] if abs(SUM) < result[0]: result[0] = abs(SUM) result[1] = (sol[std],sol[start],sol[end]) if SUM < 0: start += 1 else : end -= 1 print(" "...
[백준 2342번] Dance Dance Revolution (Python3) import sys input = sys.stdin.readline import heapq INF = 10**9 DDR = list(map(int,input().split())) DDR.pop() def force(now,next): if now == next: return 1 l1,r1 = foot[now] l2,r2 = foot[next] set1 = {l1,r1} set2 = {l2,r2} if set1&set2: if (l1+r1+l2+r2)%2 == 1: return 3 else: return 4 return INF N = len(DDR) if N == 0: print(0) else: DP = [[INF]*(N) for i in range(6)] foot = [[1,2],[1,3],[1,4],[..