목록DP (13)

jae_coding

(백준 알고리즘 문제풀이) 12865번 평범한 배낭

문제 문제 링크 문제 접근 가지고 다닐 배낭에 최대한 가치 있게 싸려고 한다. 여행자가 필요한 N개의 물건 (무게 W, 가치 V, 최대 K무게를 가질 수 있다.) 출력: 여행자가 배낭에 넣을 수 있는 최대 가치의 합 dp matrix: 행(K+1), 열(N+1) case1. 배낭의 허용 무게보다 넣을 무게가 크다면 i번째와 i+1번째의 넣은 무게를 같게한다. case2. 만약 허용 무게보다 작다면, 넣을 무게만큼 뺀 dp확인 후 현재 무게와 더하여 최대 값을 dp의 i번째에 저장한다. 코드 import sys # N: 물품의 수, K: 여행자가 버틸 수 있는 무게 N, K = map(int, sys.stdin.readline().split()) # W: 물건의 무게, V: 물건의 가치 elements =..
알고리즘 문제/백준 2022. 7. 6. 15:48
(백준 알고리즘 문제풀이) 11052번 카드 구매하기

문제 문제 링크 문제 접근 dp를 활용하는게 효율적인 코드를 만들 것 같다. 개수에 따라서 최대 값을 dp에 저장시킴으로써 정답을 도출할 수 있을 것으로 예상했다. 코드 import sys N = int(sys.stdin.readline()) P = list(map(int, sys.stdin.readline().split())) dp = list([0] * (N + 1)) for i in range(1, N+1): for j in range(1, i+1): dp[i] = max(dp[i], dp[i-j] + P[j-1]) print(dp[len(dp)-1]) 느낀점 파이썬에서 dp를 이용하기 위해서 list의 개수를 두번째 for 를 이용하기 위해서 N + 1개로 만들어주어야 하는 것을 깨닫게 되었다. ..
알고리즘 문제/백준 2022. 7. 5. 23:43
(백준 알고리즘 문제풀이) 10057번 오르막 수

문제 문제 링크 문제 접근 비트 마스킹을 통해서 문제를 풀어봐야겠다. 이 문제 또한 문제의 패턴을 잘 파악해야 한다. 내가 생각한 패턴은 표와 같이 생각을 해보았다. A[n][0] = 1, 일반화 공식: A[n][m] = A[n-1][m] + A[n][m-1] 0 1 2 3 4 5 6 7 8 9 1자리 1 1 1 1 1 1 1 1 1 1 2자리 1 1 + 1 = 2 2 + 1 = 3 4 5 6 7 8 9 10 3자리 1 3 6 10 15 21 28 36 45 55 코드 import sys N = int(sys.stdin.readline()) lst = list([1] + [0] * 9 for _ in range(N)) lst[0] = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] for i in..
알고리즘 문제/백준 2022. 7. 5. 21:43
Prev 1 2 Next