Algorithm475 [파이썬] 백준 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. [파이썬] 백준 12904 : A와 B (골드5) [파이썬] 백준 12904 : A와 B (골드5)https://www.acmicpc.net/problem/12904풀이방향성 생각start to end로 BFS처럼 진행하면 $2^1000$이라서 메모리 초과.반대로 end to start로 진행하면, 선택지는 하나밖에 없음.마지막이 A이면 A 제거.마지막이 B이면 B 제거하고 뒤집기.계속 문자열을 제거하면서 start 문자가 나오면 가능, 아니면 불가능. 전체코드start = input()end = input()answer = 0while True: # 문자열 둘이 같아졌으면 탈출 if start == end: answer = 1 break # end를 계속 제거했음에도 불구하고, start를 못찾은 경우 탈출 .. 2024. 12. 24. 이전 1 ··· 32 33 34 35 36 37 38 ··· 119 다음
