320x100 DP17 [CLASS 4]백준 2096번 - 내려가기 2096번 : 내려가기 이전에 비슷한 DP문제를 풀어본적이 있어서 드물게 빠르게 풀 수 있는 문제였다. 풀고나서 알았는데 이런 문제를 슬라이딩 윈도우 라고 부르나보다. 다만 주의할 점은 메모리 제한이 4MB로 정해져 있기 때문에 100만 길이의 리스트를 만들면 십중팔구 메모리 초과에 걸릴 것이다. 따라서 그냥 한줄씩 입력받으면서 DP를 수행하면 된다. 내 코드: # dawitblog.tistory.com/154 from sys import stdin input = stdin.readline n = int(input()) a,b,c = map(int,input().split()) current_max = [a,b,c] current_min = [a,b,c] for _ in range(n-1): a,b,c .. 2021. 5. 10. [CLASS 4]백준 17070번 - 파이프 옮기기 1 17070번 - 파이프 옮기기 1 처음 보고 BFS로 풀리겠거니~ 해서 그냥 BFS로 질렀다. 빠르게 작성하고 테스트 케이스도 잘 돌아가서 빠르게 제출했다. 내 코드(BFS,시간 초과): # dawitblog.tistory.com/146 from sys import stdin from collections import deque input = stdin.readline # 입력 n = int(input()) mat = [] for _ in range(n): mat.append(list(map(int,input().split()))) # (r,c,status) status는 0 -> 가로 , 1 -> 세로 , 2 -> 대각선 q = deque([(0,1,0)]) # 경우의 수 변수 count = 0 whi.. 2021. 4. 28. [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]백준 9251번 - LCS 9251번 : LCS 다른 방법이 딱히 떠오르지 않는다면 DP로 접근하는게 좋은 것 같다. 이 문제를 풀 때 두 단계가 있다고 하면, 먼저 이 문제가 DP로 풀린다는 것을 알기 전과 후로 나눌 수 있을 것 같다. 이전에도 이와 비슷한 문제를 푼 적이 있었는데, 그때는 연속된 수열만 취급하는 문제였기 때문에 좀더 풀기 쉬웠다. 그러나 이 문제는 연속되지 않아도(서로 떨어져 있어도) 취급하기 때문에 조금 더 어렵다. 내 코드: # dawitblog.tistory.com # 입력 s1 = input() s2 = input() l1 = len(s1) l2 = len(s2) # dp 테이블 dp = [[0]*(l2+1) for _ in range(l1+1)] for i in range(l1): for j in r.. 2021. 3. 22. 이전 1 2 3 4 5 다음
