본문 바로가기

Algorithm/Dynamic Programming69

[파이썬] 백준 15486 : 퇴사2 (골드5) [파이썬] 백준 15486 : 퇴사2 (골드5)https://www.acmicpc.net/problem/15486풀이방향성 생각N이 150만이라 바텀업으로 $O(N)$으로 푸는게 합리적으로 보인다.전체코드# Solution 1import sysinput = lambda: sys.stdin.readline().rstrip()N = int(input())arr = [tuple(map(int, input().split())) for _ in range(N)]dp = [0]*(N+1)for t in range(N): Tt,Pt = arr[t] nt = t+Tt if nt 코멘트Solution 1: 바텀업dp size를 N으로 할거면 정산 날짜를 t+Tt-1로 잡아서 강연이 마무리 되는 날에 업데.. 2024. 12. 30.
[파이썬] 백준 11054 : 가장 긴 바이토닉 부분 수열 (골드4) [파이썬] 백준 11054 : 가장 긴 바이토닉 부분 수열 (골드4)https://www.acmicpc.net/problem/1105풀이방향성 생각$O(N^3)$ 바텀업으로도 풀이가 가능해보이긴 한다.탑다운으로 안푼지 오래돼서 연습할겸 탑다운 풀이.같은 인덱스에 / 마지막 값 prev를 들고 / up 상태로 접근전체코드import syssys.setrecursionlimit(10**6)N = int(input())arr = list(map(int, input().split()))dp = {}def dfs(idx,prev,up): # 종료조건 if idx == N: return 0 # 메모제이션 state = (idx,prev,up) if state in dp: .. 2024. 12. 26.
[파이썬] 백준 5557 : 1학년 (골드5) [파이썬] 백준 5557 : 1학년 (골드5)https://www.acmicpc.net/problem/5557풀이방향성 생각DFS + DP로 풀이배열을 탐색하면서 cumsum이 0미만, 20초과가 되는 경우에서 가지치기를 해준다.마지막 인덱스에 도달하면 등식 성립 확인해서 맞으면 1, 아니면 0.이외의 경우에는 탐색 + 메모제이션. 전체코드N = int(input())arr = list(map(int,input().split()))dp = {}def dfs(idx,cumsum): # 탈출조건 if cumsum 20: return 0 # 종료조건 if idx == N-1: return 1 if cumsum == arr[-1] else 0 # 메모제이션 .. 2024. 12. 25.
[파이썬] 백준 10251 : 운전 면허 시험 (플레5) [파이썬] 백준 10251 : 운전 면허 시험 (플레5)https://www.acmicpc.net/problem/10251풀이방향성 생각상태 공간 나누기x좌표, y좌표, x,y에 들어오는 진입 방향, 누적 회전 수상태공간 나누는 기준이 G가 아닌건, G 범위가 너무 크다.G 공간을 리스트로 나누거나 딕셔너리로 나눠도 메모제이션이 되지 않을 가능성이 매우 높아서 BFS랑 다를바가 없다.전체코드import sysinput = lambda : sys.stdin.readline().rstrip()T = int(input())for _ in range(T): H,W,L,G = map(int, input().split()) # 가로이동 : hor[i][j] (j,i)에서 (j+1,i)로 이동 hor.. 2024. 11. 19.

티스토리툴바