Algorithm/Dynamic Programming69 [파이썬] 백준 20181 : 꿈틀꿈틀 호석 애벌레 - 효율성 (골드2) [파이썬] 백준 20181 : 꿈틀꿈틀 호석 애벌레 - 효율성 (골드2)https://www.acmicpc.net/problem/20181풀이방향성 생각슬라이딩 윈도우를 통해서, 각 인덱스를 시작점으로 정하고 먹었을 때 어느 구간에서 끝나는지 ends에 기록한다.또한, ends에 기록하면서 그 때의 초과 만족도를 계산한다.이후 DFS + DP를 통해서 문제풀이. 전체코드import syssys.setrecursionlimit(10**6)N,K = map(int,input().split())arr = list(map(int,input().split()))ends = []scores = []l,r = 0,0score = arr[0]while l= N: return 0 if dp[x] != .. 2025. 4. 7. [파이썬] 백준 2515 : 전시장 (골드2) [파이썬] 백준 2515 : 전시장 (골드2)https://www.acmicpc.net/problem/2515풀이방향성 생각형태는 0/1 냅색 형태의 문제이다.입력 크기를 보면 N = 30만, cost = 1000이라 2차원 배열로 만드는 것이 불가능하다.또한, 높이 조건이 걸려있어서 정렬 이후에 이전 높이차가 S 이상을 만족시키는 그림 중 가장 큰 dp값을 가져와주면 된다.가장 큰 DP 값을 가져올 때, 해당 인덱스에서 가장 큰 값을 저장할 수 있도록 DP 배열을 업데이트 해주기.단순히 인덱스를 찾고 이전 구간에서 O(N)으로 순회하면 TLE높이 차이가 S 이상을 만족시키는 그림을 찾을 때, 투포인터 / 이분탐색으로 가능하다. 파이썬import sysinput = sys.stdin.readlineN,S.. 2025. 4. 7. [파이썬] 백준 17485 : 진우의 달 여행 (Large) (골드5) [파이썬] 백준 17485 : 진우의 달 여행 (Large) (골드5)https://www.acmicpc.net/problem/17485풀이방향성 생각x,y 이외에 같은 노드에서도 방향을 기억해야하는 문제3차원 바텀업 DP로 풀이 전체코드import sysinput = sys.stdin.readlineH,W = map(int,input().split())arr = [list(map(int,input().split())) for _ in range(H)]dp = [[[10**5+1]*W for _ in range(H)] for _ in range(3)]for d in range(3): dp[d][0] = arr[0][:]dires = [-1,0,1]for y in range(1,H): for x.. 2025. 4. 7. [파이썬] 백준 1890 : 점프 (실버1) [파이썬] 백준 1890 : 점프 (실버1)https://www.acmicpc.net/problem/1890풀이방향성 생각탑다운으로 풀이중간에 0이라서 이동이 불가능한 지점은 따로 예외처리 해주기 전체코드import syssys.setrecursionlimit(10**6)N = int(input())dires = [(1,0),(0,1)]inside = lambda x,y: 0코멘트 2025. 4. 5. 이전 1 2 3 4 5 ··· 18 다음
