비트마스킹, DP문제 (백준 1480 파이썬)

비트마스킹

비트마스킹의 장점

• 간결
• 빠름
• 메모리

True False True 를 101 로 표기하는 것..

---

비트 연산

1. AND &

   • 둘다 1이면 1

     bin(0b1010 & 0b1101)
     >>> 0b1010

2. OR |

   • 둘 중 하나라도 1이면 1

     bin(0b1010 & 0b1101)
     >>> 0b1111

3. XOR ^

   • 둘이 서로 다르면 1

     bin(0b1010 & 0b1101)
     >>> 0b0111

4. SHIFT >> <<

   • a << b : a의 비트를 b칸만큼 왼쪽으로 옮김

     bin(0b0010 << 2)
     >>> 0b1000
     
     bin(0b1100 >> 2)
     >>> 0b11
     
     bin(0b1010 >> 3)
     >>> 0b1
     
     bin(0b1100 << 2)
     >>> 0b110000 #중요

5. NOT ~

   • -(x+1) 을 반환

     bin(~0b1010)
     # -(0b1010 + 1)
     # -(0b1011)
     >>> -0b1011

---

문제 풀때 사용하는 것들

#중요
bin(1 << 1)
>>> 0b10

bin(1 << 2)
>>> 0b100

bin(1 << n)
>>> 0b1(0 : n개)

# 응용

# 0b0010 을 0b1010 으로 바꾸고 싶다.
bin(0b0010 | (1 << 3))
>>> 0b1010

# 0b1111 을 0b1011 으로
bin(0b1111 ^ (1 << 2))
또는
bin(0b1111 & ~(1 << 2))

---

비트마스킹 활용 dp 문제

https://www.acmicpc.net/problem/1480

12865번 문제와 비슷한 느낌..

모든 경우의 수를 해봐야 한다. <<< for 문을 통해 모든 보석을 넣어본다.

이런 메모이제이션 문제의 경우 핵심은

dp배열의 요소가 뭘 뜻하는지 알아야한다.

이 문제의 경우

1. 현재 보석의 사용 상태가 gems 일 때, (ex. 100 이면 3번째 보석만 사용한 상태, 11001 이면 1,4,5번째 보석 사용한 상태)
2. 현재 사용 중인 가방의 위치가 bag_idx 일 때,
3. 현재 사용 중인 가방의 용량이 current_capacity 만큼 남았을 때
4. 담을 수 있는 최대의 보석 개수를 의미하도록 설계했다.

즉 dp[0][0][5] 이면
현재 보석 아무것도 사용 안한 상태, 현재 첫 번째 가방 사용 중, 용량도 5 남은 상태일 때,
담을 수 있는 최대의 보석 개수를 의미한다.

파이썬 코드

import sys
N, M, C = map(int, sys.stdin.readline().split())
gem_list = list(map(int, sys.stdin.readline().split()))

dp = [[[0 for i in range(C+1)] for j in range(M+1)] for k in range(1 << 14)]


def solution(gems, bag_idx, current_capacity) :
    # 가방 다 썼거나, 보석 다 썼으면 ?
    if gems == ((1 << N) - 1) or bag_idx >= M :
        return 0

    if dp[gems][bag_idx][current_capacity] != 0 :
        return dp[gems][bag_idx][current_capacity]

    now_answer = 0

        # 모든 보석을 돌면서 하나씩 다 넣어본다. 중요.. 
    for i in range(N) : 

        # 지금 쓸려는 보석이 이미 사용한 보석이면..?
        if (gems & (1 << i)) != 0 or gem_list[i] > C : 
            continue

        # 지금 가방에 넣을 수 있으면 ?
        if (current_capacity >= gem_list[i]) :
            now_answer = max(now_answer, solution(gems | (1 << i), bag_idx, current_capacity - gem_list[i]) + 1)
                # 못 넣으면? 다음 가방 ㄱ
        else :
            now_answer = max(now_answer, solution(gems, bag_idx + 1, C))


    dp[gems][bag_idx][current_capacity] = now_answer
    return now_answer

print(solution(0, 0, C))