개구리의 개발 블로그 개구리의 개발 블로그

냅색 분류인 것을 보고 풀었기 때문에 일단 2차원 배열을 만들어야겠다는 생각을 했다. 풀긴 했지만 코드가 깔끔하지도 않고 시간도 꽤나 오래 걸렸다. 1106번 문제를 풀기 전에 1차원 배열을 이용해 평범한 배낭 문제를 풀이하는 방법을 알아보자. 0. 일반적인 냅색 문제 풀이(1차원 / 2차원 배열 이용) 12865번 평범한 배낭 문제를 기준으로 설명하겠습니다. https://www.acmicpc.net/problem/12865 2차원 배열에서 dp[i][j]에 i번째 보석까지 j 무게를 사용했을 때 얻을 수 있는 최대 가치를 저장한다. 모든 보석에 대하여 1에서 최대 용량까지 반복문을 실행하며 dp[i][j] = max(dp[i-1][j], dp[i-1][j-cost]+ benefit)로 갱신한다. 2차..

백준 2208번 보석줍기 파이썬 출처 - https://www.acmicpc.net/problem/2208 2208번: 보석 줍기 화영이는 고대 유적을 탐사하던 도중 보석을 발견했다. 유적 속에는 N(1 ≤ N ≤ 100,000)개의 보석들이 일렬로 놓여 있었다. 각각의 보석의 가치는 다를 수 있기 때문에, 화영이는 가급적 많은 이득 www.acmicpc.net 까다로운 DP를 풀어보고 싶어서 검색해서 풀었는데 생각보다 쉽게 풀렸다. 투 포인터 생각도 났는데 최댓값을 구해야 되는 문제이기 때문에 일단 구간합부터 구하고 시작했다. 1. 풀이 보석은 반드시 M개 이상 연속해서 주워야 한다. 즉 길이가 M이상인 구간합 중 최대를 찾으면 된다. dp[i][0]에는 현재 보석을 선택하지 않았을 때 최대 구간합을 ..