320x100 PS84 [CLASS 4]백준 13549번 - 숨바꼭질 3 13549번 : 숨바꼭질 3 숨바꼭질 2에서 좀 힘들었던 경험이 있어서 3은 더 어렵지 않을까 걱정했지만 오히려 엄청 쉽게 풀 수 있었다. 이 문제에서 특이한 점은 순간이동은 시간을 소비하지 않는다는 것이다. BFS를 수행하되 어떤 점에서 2배를 계속 하면서 큐에 한번에 다 추가해 주어야 한다. 그래야 큐 안에 시간이 2초 이상 차이나는 경로가 추가되지 않는다. 내 코드: # dawitblog.tistory.com from collections import deque n,k = map(int,input().split()) if n >= k: print(n-k) exit() limit = 2*k-n q = deque([(n,0)]) visited = [False] * (limit+1) visited[n] .. 2021. 3. 29. [CLASS 4]백준 12865번 - 평범한 배낭 12865번 : 평범한 배낭 DP중에서도 대표적인 냅색(Knapsack,배낭) 문제이다. 처음 푼다면 좀 어지러울 수 있는데, 물품을 하나씩 검사하면서 최대 가치를 갱신한다는 점에서 정말 DP스러운 문제라고 생각한다. 내 코드(1차): # dawitblog.tistory.com from sys import stdin input = stdin.readline n, k = map(int,input().split()) l = [0] for _ in range(n): w, v = map(int,input().split()) # 버틸 수 있는 무게를 넘는 물건은 추가하지 않음 if w a만큼 버틸수 있는 가방에 b번째 물건까지 넣었을 때 최대가치 dp = [[0]*(n+1) for _ in range(k+1)] .. 2021. 3. 26. [CLASS 4]백준 12851번 - 숨바꼭질 2 12851번 : 숨바꼭질 2 숨바꼭질 1 문제를 푼 기억이 있어서 2도 엄청 쉽게 풀 수 있을 줄 알았는데 착각이었다.. 1과의 차이점은 최단시간으로 가는 서로 다른 최단경로가 몇가지 있는지까지 찾아야 하는 것인데, 이게 생각보다 쉽게 찾아지지가 않았다. 내 코드: # dawitblog.tistory.com from collections import deque n, k = map(int,input().split()) if n >= k: print(n-k,1,sep='\n') exit() check = [[-1,0] for _ in range(100001)] q = deque() q.append(n) check[n] = [0,1] while q: now = q.popleft() for new in (now.. 2021. 3. 25. [CLASS 4]백준 9663번 - N-Queen 9663번 : N-Queen 엄청 유명한 N-Queen문제이다. 이 문제는 시간 제한이 특이하게 10초이다. 그래서 파이썬으로도 가능할 줄 알았는데... 지금의 내 실력으로는 도저히 이거보다 빠른 코드를 작성하기가 힘들 것 같다... 내 코드: # dawitblog.tistory.com def find(r): global count if r == n: # n줄 까지 도달했다면 1가지 경우 추가 count += 1 return for c in range(n): # 대각선 값 s = r + c b = r - c if col[c] and slash[s] and backSlash[b]: col[c] = slash[s] = backSlash[b] = False find(r+1) col[c] = slash[s] =.. 2021. 3. 23. 이전 1 ··· 3 4 5 6 7 8 9 ··· 21 다음
