백준 12865 평범한 배낭

2020. 9. 7. 10:58·알고리즘/BOJ

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

이번에 풀어본 문제는 대표적이라 하는(?) 냅색 문제이다.

냅색 문제는 가방에 무게와 가치가 주어졌을 때, 가방의 무게 안에 가장 큰 가치를 챙기게 하는 로직으로 가야한다.

그리디한 방식으로는 전부 반례가 있다.

 

#include <iostream>
using namespace std;

int n, k, ar[101][2], d[101][100001];

int main() {
	cin >> n >> k;
	for (int i = 1; i <= n; i++) cin >> ar[i][0] >> ar[i][1];

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= k; j++) {
			if (j < ar[i][0]) d[i][j] = d[i - 1][j];
			else d[i][j] = max(d[i - 1][j - ar[i][0]] + ar[i][1], d[i - 1][j]);
		}
	}
	//for (int i = 1; i <= n; i++) {
	//	for (int j = 0; j <= k; j++) {
	//		cout << d[i][j] << ' ';
	//	}
	//	cout << '\n';
	//}
	cout << d[n][k] << endl;

	return 0;
}

 

바텀업으로 풀어봤다. 주목해야 할 코드는

		if (j < ar[i][0]) d[i][j] = d[i - 1][j];
		else d[i][j] = max(d[i - 1][j - ar[i][0]] + ar[i][1], d[i - 1][j]);

이 코드다. 

이중 포문으로 j를 하나씩 올려가면서 현재 가방의 무게보다 작다면, 그 윗 단계의 가방을 가져오고,

j가 현재 가방의 무게 이상이라면 이번 가방의 가치를 포함한 것과, 포함하지 않고 전 단계의 가방을 가져온 것의 합 중 

큰 것을 가져온다.

 

주석 처리한 코드로 살펴보면 어떤 식으로 진행되는지를 알 수 있다. 식은 간단하지만 이해하는데는 생각보다 오래 걸린다.

 

#include <iostream>
using namespace std;

int n, k, ar[101][2], d[101][100001];

int go(int i, int w) {
	if (i == n + 1) return 0;
	if (d[i][w]) return d[i][w];
	int n = 0, n2;
	if (w + ar[i][0] <= k) n = ar[i][1] + go(i + 1, w + ar[i][0]);
	n2 = go(i + 1, w);
	return d[i][w] = n > n2 ? n : n2;
}

int main() {
	cin >> n >> k;
	for (int i = 1; i <= n; i++) cin >> ar[i][0] >> ar[i][1];

	cout << go(1, 0) << endl;

	return 0;
}

 

이번에는 무게를 함수 인자로 넘겨줘서 메모이제이션을 해줬다.

	if (w + ar[i][0] <= k) n = ar[i][1] + go(i + 1, w + ar[i][0]);
	n2 = go(i + 1, w);
	return d[i][w] = n > n2 ? n : n2;

이번 물건의 무게를 포함한 무게가 버틸 수 있는 무게를 넘지 않았다면 넣어보고, 그냥 넣지 않고 스킵한 것중 큰 값을 

dp에 넣어서 리턴해준다.

 

#include <iostream>
#include <algorithm>
using namespace std;

int d[100001], ar[101][2];

int main() {
	int n, k;
	cin >> n >> k;

	for (int i = 0; i < n; i++) cin >> ar[i][0] >> ar[i][1];

	for (int i = 0; i < n; i++) {
		for (int j = k - ar[i][0]; j >= 0; j--) {
			d[j + ar[i][0]] = max(ar[i][1] + d[j], d[j + ar[i][0]]);
		}
	}
	cout << d[k];

	return 0;
}

 

다 풀고 풀이를 확인하던 중에 어떤 분이 1차원 dp로 푸는 걸 보고 따라해봤다.

		for (int j = k - ar[i][0]; j >= 0; j--) {
			d[j + ar[i][0]] = max(ar[i][1] + d[j], d[j + ar[i][0]]);
		}

 

전체 k에서 가방의 무게를 빼주고 뒤에서부터 인덱스를 채우는 식이다.

i가 끝날때마다 가방 하나씩 체크하고 다시 갱신하는 식이라 시간복잡도가 훨씬 줄어듦을 예상할수 있다.

참신한 방법이라 생각했다.

 

냅색 문제는 dp의 대표적인 유형이라는데 비슷한 유형의 문제가 나오면 잘 풀 수 있도록 노력해봐야겠다.

'알고리즘 > BOJ' 카테고리의 다른 글

백준 2331 반복수열  (0) 2020.09.08
백준 10451 순열 사이클  (0) 2020.09.07
백준 13305 주유소  (0) 2020.09.07
백준 2981 검문  (0) 2020.09.07
백준 19621, 19622 회의실배정 2, 3  (0) 2020.09.06
'알고리즘/BOJ' 카테고리의 다른 글
  • 백준 10451 순열 사이클
  • 백준 13305 주유소
  • 백준 2981 검문
  • 백준 19621, 19622 회의실배정 2, 3
khyu2
khyu2
  • khyu2
    dev log
    khyu2
  • 전체
    오늘
    어제
    • 분류 전체보기
      • 알고리즘
        • BOJ
        • Programmers
        • Algorithm
        • SWEA
      • 개발
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    BFS
    피사노 주기
    트리
    조합
    GREEDY
    MST
    이분 탐색
    완전탐색
    프로그래머스
    구현
    SWEA
    우선순위 큐
    알고리즘
    다익스트라
    dp
    소수
    냅색
    완전 탐색
    시뮬레이션
    이분탐색
    코딩테스트 연습
    BOJ
    유니온 파인드
    분할 정복
    큐
    팰린드롬
    크루스칼
    행렬 제곱
    피보나치 수
    dfs
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
khyu2
백준 12865 평범한 배낭
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.