Algorithm475 [파이썬] 백준 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. [파이썬] 백준 11000 : 강의실 배정 (골드5) [파이썬] 백준 11000 : 강의실 배정 (골드5)https://www.acmicpc.net/problem/11000풀이방향성 생각정렬 + 스위핑/힙 전체코드import sysinput = sys.stdin.readlineN = int(input())arr = []for _ in range(N): s,e = map(int,input().split()) arr.append((s,1)) arr.append((e,-1))arr.sort()answer,cur = 0,0for _,new in arr: cur += new answer = max(answer,cur)print(answer)import heapq as hqimport sysinput = sys.stdin.readlineN .. 2025. 4. 6. 이전 1 ··· 5 6 7 8 9 10 11 ··· 119 다음
