본문 바로가기

분류 전체보기

(402)
[백준 11025번] 요세푸스 문제 3 (Python3) N,K = map(int,input().split()) last = 0 for n in range(1,N+1): last = (K+last)%n print(last+1) 다이나믹 프로그래밍으로 해결하였다. 메모리 제한이 매우 작은것이 오히려 힌트가 되는 문제였다. 메모리 제한이 넉넉했다면 오히려 아이디어를 떠올리기 힘들었을 수도 있다. 하지만 메모리 제한은 매우 작은데 N의 범위는 500만이나 되다 보니, 크기 N의 배열을 이용하는 풀이나 세그먼트 트리나 팬윅트리같은 풀이를 애초에 배제할 수 있었고, 아이디어를 쉽게 떠올릴 수 있었다. 아이디어는 이러하다. 크기 n의 요세푸스 마지막 숫자가 x라고 가정하자. n+1명의 사람들이 있을 때, 가장 먼저 제거되는 사람은 K번째 사람이다. 그럼 남은 사람들의 숫..
[백준 14868번] 문명 (Python3) import sys,collections input = sys.stdin.readline dy = [1,-1,0,0]; dx = [0,0,1,-1] def BFS(): connect = 0 while dq: y,x,k,t = dq.popleft() if visited[y][x]: continue visited[y][x] = k for i in range(4): y1,x1 = y+dy[i],x+dx[i] if N>y1>=0 and N>x1>=0: k1 = visited[y1][x1] if k1: if find(k)==find(k1): continue parent[parent[k1]] = parent[k] connect += 1 if connect == K-1: return t else: dq.append(..
[백준 9376번] 탈옥 (Python3) import sys,collections input = sys.stdin.readline dy = [1,-1,0,0]; dx = [0,0,1,-1] def check(y,x): MIN = [1e5]*3 for i in range(4): y1,x1 = y+dy[i],x+dx[i] if N>y1>=0 and M>x1>=0: for n in range(3): MIN[n] = min(MIN[n],visited[n][y1][x1]) return sum(MIN) def BFS(y,x): visited = [[1e5]*M for i in range(N)] dq = collections.deque([(y,x,0)]) while dq: y,x,c = dq.popleft() if visited[y][x]y1>=0 and ..
[백준 2507번] 공주 구하기 (Python3) import sys input = sys.stdin.readline def DFS(x1,x2): DP[x1][x2] = 0 M = max(x1,x2)+1 for next in range(M,N-1): if not graph1[x1][next]: break if DP[next][x2]==-1: DFS(next,x2) DP[x1][x2] += DP[next][x2] for next in range(M,N-1): if not graph2[x2][next]: continue if DP[x1][next]==-1: DFS(x1,next) DP[x1][x2] += DP[x1][next] DP[x1][x2] += int(graph1[x1][-1]==graph2[x2][-1]==1) DP[x1][x2] %= 1000 N..
[백준 9520번] NP-hard (Python3) N = int(input()) graph = [[*map(int,input().split())] for _ in range(N)] DP = [[1e9]*N for i in range(N)] DP[0][0] = 0 for start in range(1,N): for end in range(start): DP[start][end] = min(DP[start][end],graph[start][start-1]+DP[start-1][end]) DP[start][start-1] = min(DP[start][start-1],graph[start][end]+DP[start-1][end]) print(min(DP[-1])) 다이나믹 프로그래밍으로 해결하였다. 문제 해석도 까다롭고 풀이 아이디어도 쉽지 않은 문제였다. 일..
[백준 7982번] 순열 그래프의 연결성 판별 (Python3) N = int(input()) seq = [*map(int,input().split())] S = []; MAX = 0 for i in range(N): if MAX==i: S.append([]) n = seq[i] MAX = max(MAX,n) S[-1].append(i+1) print(len(S)) for s in S: print(len(s),*s) 비둘기집 원리를 이용하여 해결하였다. 아이디어를 떠올리기 쉽지 않았던 문제였다. 디지털 비디오 디스크 [백준 9345번] 디지털 비디오 디스크(DVDs) (Python3) (tistory.com) 문제처럼 숫자가 1~N까지 한개씩 있다는 것에 주의해야 하는데, 저 문제에서 내가 생각한 풀이와 다르게 비둘기집을 이용한 풀이가 있다는 것을 공부한 경험이 아이..
[백준 17398번] 통신망 분할 (Python3) import sys,math input = sys.stdin.readline def find(x): if parent[x]!=x: parent[x] = find(parent[x]) return parent[x] N,M,Q = map(int,input().split()) graph = [[0,*map(int,input().split())] for i in range(M)] for i in range(Q): graph[int(input())-1][0] = Q-i graph.sort() parent = [i for i in range(N+1)]; group = [1]*(N+1) result = 0 for i,x,y in graph: if find(x)==find(y): continue if i: result ..
[백준 3679번] 단순 다각형 (Python3) import sys,math input = sys.stdin.readline for _ in range(int(input())): data = [*map(int,input().split())]; N = data[0] co = sorted([(data[i*2+2],data[i*2+1],i) for i in range(N)]) y0,x0,n0 = co[0]; stack = [] for i in range(1,N): y,x,n = co[i] d = math.sqrt((x-x0)**2+(y-y0)**2) stack.append((int((x0-x)/d*1e9),int(d*1e9),n)) stack.sort() cos0 = stack[-1][0] for i in range(N-1): if stack[-i-1][0..