백준 12920 평범한 배낭 2
출처: https://www.acmicpc.net/problem/12920 이 문제는 어려워서 인터넷 보고 풀이 검색하고 풀이 해석한 다음에 다시 혼자 풀어봤다. 포인트1: n개까지 채울수 있다고 dp 배열을 어떤 물건을 1개 가지는 경우, 2개 가지는 경우, ... n개 가지는 경우를 다 따로 생각할 필요가 없음!! 왜냐면 이진법으로 모든 수를 나타낼 수 있기 때문에. 1, 2, 4, 8, ... 개 챙기는 경우만 고려. 포인트2: tot랑 flag 만든 이유. 이진법으로 한다고 1, 2, 4, 8, ... 로 하면 안됨. 배낭 최대 무게가 1~10000까지 아무 숫자로 주어지는데 2의 n승을 다 배열에 넣어버리면 합했을 때 배낭 최대 무게를 넘어버림!! 포인트3: dp 배열 채울 때 뒤에서부터 채우고..
2018. 11. 9.