728x90 DP18 [백준] 15988번: 1, 2, 3 더하기 3 - python https://www.acmicpc.net/problem/15988 전에 풀었던 1,2,3더하기와 거의 일치한 문제중간중간 나머지 연산과 시간초과로 인하여 처음부터 한번에 연산을 진행 후 마지막에 출력하는 형태로 변환import sysinput = sys.stdin.readlinen = int(input())dy = [0] * (1000001)dy[0] = 1dy[1] = 1dy[2] = 2dy[3] = 4dy[4] = 7dy[5] = 13for i in range(5, 1000001): dy[i] = dy[i-1] % 1000000009 + dy[i-2]% 1000000009 + dy[i-3]% 1000000009for i in range(n): a = int(input()) p.. 2024. 5. 7. [백준] 15486번: 퇴사 2 - python https://www.acmicpc.net/problem/15486 아까 푼 퇴사 1하고 뭐가 다른지 잘 모르겠는 문제 T, P에 값을 저장한 뒤, 뒤에서부터 값이 딱 퇴사일과 같을 경우에만 dp에 값을 저장하면서 저장시에는 전 날, T전 날 + P 가격과 비교하면서 값을 저장해준다. 만약 값이 퇴사일을 넘을시에는 전에 있던 값을 그대로 옮기면서 첫날까지 오면 첫날에 최대값이 나오게 된다.n = int(input())T = []P = []dp = [0] * (n+1)for _ in range(n): a, b = map(int, input().split()) T.append(a) P.append(b)for i in range(n-1, -1 , -1): if i+T[i] 완성 2024. 5. 6. [백준] 14501번: 퇴사 - python https://www.acmicpc.net/problem/14501 14501번: 퇴사첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다.www.acmicpc.net 배울게 참 많은 문제 첫번째 아이디어DFS를 이용하여 상태트리를 생성하여 계산하는 방식과N = int(input())def DFS(L, sum): global res if L == N+1: if res 두번째는 DP를 이용하여 최대값을 계속 저장해나가는 방식이다. n = int(input())schedule = []dp = [0] * (n+1)for i in range(1,n+1): a, b = map(int, input().split()) schedule.append([a,b])for i in ra.. 2024. 5. 6. [백준] 12865번: 평범한 배낭 - python https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)www.acmicpc.net 냅색 알고리즘 응용문제 n, m = map(int, input().split())dp = [0] * (m+1)for _ in range(n): w, v = map(int, input().split()) # 역순으로 루프를 돌며 최대 가치 계산 for j in range(m, w-1, -1): dp[j] = .. 2024. 4. 11. 이전 1 2 3 4 5 다음 728x90
