[백준] 1535 안녕

비트를 이용한 완전탐색 또는 DP로 해결할 수 있는 문제다

삼성 소프트웨어 역량테스트에 자주 나오는 유형같다

1. 먼저 비트를 이용한다면

인사한사람은 1 안한사람은 0으로 표현해서 모든 수를 표현해보면 된다.

최대 (1<<20) 개를 보기 때문에 100 만번정도 보게 된다.

for문으로 모든 경우를 확인하며

1이 있는지 확인하고 만약 있다면 체력을 빼고 기쁨을 넣어주면 된다!

소스코드

#include <iostream>
#include <algorithm>
using namespace std;
int n, L[22], J[22];
 
int main() {
    scanf(" %d", &n);
    for (int i = 0; i < n; i++) scanf(" %d", &L[i]);
    for (int i = 0; i < n; i++) scanf(" %d", &J[i]);
 
    int ans = 0;
    for (int i = 0; i < (1 << n); i++) {
        int hp = 100, happy = 0;
        for (int j = 0; j < n; j++) {
            if (i&(1 << j)) {
                hp -= L[j];
                happy += J[j];
            }
            if (hp <= 0)     continue;
            ans = max(ans, happy);
        }
    }
    printf("%d\n", ans);
}

2. DP를 이용한다면 2차 테이블을 잡아서 문제를 풀 수 있다.

DP[N(위치)][K(체력)] => N번째 까지 봤고 체력이 K남았을 때 최대기쁨

이렇게 테이블을 잡고 재귀로 짠다면 쉽게 풀 수 있다!

 

1. go 함수에서 만약 위치가 마지막위치를 넘는다면 0을 리턴한다

2. ret의 값에는 현재를 보지않고 건너뛰었을 때의 값을 저장한다

3. 만약 현재를 봤을 때 체력이 0보다 크다면 그 때 현재값을 보며 최대값을 찾는다!

소스코드

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int n, L[22], J[22], d[22][101];
 
int go(int pos, int hp) {
    if (pos == n) return 0;
    int&ret = d[pos][hp];
    if (ret != -1) return ret;
    ret = go(pos + 1, hp);
    if (hp - L[pos] > 0) ret = max(ret, go(pos + 1, hp - L[pos]) + J[pos]);
    return ret;
}
 
int main() {
    memset(d, -1, sizeof(d));
    scanf(" %d", &n);
    for (int i = 0; i < n; i++) scanf(" %d", &L[i]);
    for (int i = 0; i < n; i++) scanf(" %d", &J[i]);
 
    printf("%d\n", go(0, 100));
}