본문 바로가기

분류 전체보기

 (402)
[백준 1981번] 배열에서의 이동 (Python3) from collections import * dy = [1,-1,0,0]; dx = [0,0,1,-1] def BFS(): dq = deque([(0,0,board[0][0],board[0][0])]) while dq: y,x,m,M = dq.popleft() if DP[y][x][m]=0 and N>x1>=0: dq.append((y1,x1,min(m,board[y1][x1]),max(M,board[y1][x1]))) N = int(input()) board = [[*map(int,input().split())] for i in range(N)] DP = [[[400]*201 for i in range(N)] for i in range(N)] BFS() print(min(DP[-1][-1][i]-i ..
[백준 2014번] 소수의 곱 (Python3) from heapq import * K,N = map(int,input().split()) prime = [*map(int,input().split())] hq = [1]; nums = set() MAX = 0 for _ in range(N+1): x = heappop(hq) for p in prime: if p*x in nums or len(hq)>N and p*x>MAX: continue MAX = max(MAX,p*x) heappush(hq,p*x); nums.add(p*x) print(x) 우선순위 큐를 이용하여 해결하였다. 풀이 자체는 쉽게 떠올릴 수 있다. 하지만 숫자가 큰 탓인지 커팅을 하지 않고 그냥 무지성으로 코드를 짜면 메모리 초과가 발생한다. 따라서 이를 처리해주는 것이 필요하다. 풀..
[백준 2532번] 먹이사슬 (Python3) import sys input = sys.stdin.readline from bisect import * N = int(input()) animal = set() for _ in range(N): i,x,y = map(int,input().split()) animal.add((-x,y)) animal = sorted(animal) DP = [0] for a,b in animal: if b>=DP[-1]: DP.append(b) else: DP[bisect_right(DP,b)] = b print(len(DP)-1) LIS로 해결하였다. 아이디어를 떠올리기 쉽지 않았던 문제였다. 처음에는 정렬+스택 문제라고 생각했는데, 정렬+스택으로 풀 수 없다는 사실을 깨달았다. LIS를 이용한다는 아이디어만 떠올리면 ..
[백준 1365번] 꼬인 전깃줄 (Python3) from bisect import * N = int(input()) seq = [*map(int,input().split())] DP = [0] for n in seq: if n>DP[-1]: DP.append(n) else: DP[bisect_left(DP,n)] = n print(N+1-len(DP)) 전깃줄 - 2 [백준 2568번] 전깃줄 -2 (Python3) (tistory.com) 문제의 하위호환 문제 N과 LIS 길이의 차를 출력해주면 된다. 여담) 내 풀이가 파이썬 기준 성능 1위가 되었다.
[백준 15647번] 로스팅하는 엠마도 바리스타입니다 (Python3) import sys input = sys.stdin.readline sys.setrecursionlimit(1
[백준 17834번] 사자와 토끼 (Python3) import sys input = sys.stdin.readline sys.setrecursionlimit(10**6) def DFS(now,sign): global gameover if gameover: return visited[now] = sign for next in graph[now]: if visited[next]==sign: gameover = 1 if not visited[next]: DFS(next,-sign) N,M = map(int,input().split()) graph = [[] for i in range(N+1)] for _ in range(M): x,y = map(int,input().split()) graph[x].append(y); graph[y].append(x) visi..
[백준 13912번] 외계 생물 (Python3) from math import * mod = 10**9+7 comb = [factorial((1
[백준 1300번] K번째 수 (Python3) def cal(x): n = min(int(x**0.5),N) cnt = 0; same = 0 for i in range(1,n+1): m = min(x//i,N) cnt += m same += int(x==m*i)*2 return cnt*2-n**2+1, same-int(n**2==x) def find(x,c): k,s = cal(x) if kK: return find(x-2**c,c-1) return x N = int(input()); K = int(input()) print(find(1

티스토리툴바