[BOJ|python]백준 1562 비트마스킹 (+DP)

비트마스킹을 이용하면 굳이 배열을 쓰지 않아도 되므로 메모리도 절약될 뿐만 아니라 
배열의 index로도 쓸 수 있어(0001은 1로, 0010은 2로 쓸 수 있다.) 매우 강력한 툴이다!
주로 있다/없다 의 이분법적 현상을 반영해서 표현할 수 있다.

이것만 알면..!! 된다!!

& -> 모두 1일때 1반환
| -> 하나라도 1일때 1 반환 / 모두 0일 때 0반환
^ -> 대응하는 두 비트가 서로 다를 때 1반환
>> -> 오른쪽으로 비트 옮김 100>>2:1
★삽입 시! i번째 비트를 i값으로 변경할 때
10101에서  11101 만들고 싶다면  10101 | 1<<3
★삭제 시!
10101에서 10001로 만들고 싶다면 10101 & ~1<<3
★조회 시!
i번째 비트가 무슨 값인지 알라면 10101 &(1<<i) 했을 때 1나오면 1이고 0나오면 0

백준 1562번
TIP
*DP가 3차원으로 진행되면 복잡해보일 수 있는데, 3차원을 그냥 머릿속으로 그리지 말고 조건만 만족하자고 생각하고 구현하면 그리 복잡하지 않다.
*너무 복잡하면 그냥 2차원을 계속 갱신하면서 2차원 박스를 여러 개 만들어나갈 것.

import sys
input=sys.stdin.readline

#List[끝나는수 0~9][몇자리수인지][비트마스크]=해당숫자 나열
List=[[[0 for _ in range(1024)] for _ in range(101)] for _ in range(10)]

#init
for i in range(1,10):
    List[i][1][1<<i]=1

#규칙에 맞는 점화식
#1,2,3,,,8까지의 숫자로 끝나는 경우에는 뒤에 두 개가 붙을 수 있으나 
#9로 끝나는 경우에는 뒤에 8만 붙을 수 있다.
#N-1로 끝나는 숫자들 중에서 가져와서 판단해서 넣고, 이 때 비트마스킹을 사용해서 0부터 9 중 뭘 썼는지 파악
for j in range(2,101):
    for k in range(10):
        for l in range(1024):
            if k==0: #1로 끝나는 애에서민 가져와야 한다.
                List[0][j][l|1<<(0)]+=(List[1][j-1][l])
            elif k==9: #8로 끝나는 애에서만 가져올 수 있다.
                List[9][j][l|1<<(9)]+=(List[8][j-1][l])
            else:
                List[k][j][l|1<<(k)]+=(List[k-1][j-1][l])
                List[k][j][l|1<<(k)] %=1000000000
            
                List[k][j][l|1<<(k)]+=(List[k+1][j-1][l])
                List[k][j][l|1<<(k)]  %=1000000000

N=int(input())
sum=0

for i in range(10):
    sum+=(List[i][N][1023]%1000000000) #N자리 수 중에서 / i로 끝나는 수 중 / 0부터 9 다 있는 수

print(sum%1000000000)

 

어딘진 모르겠으나 기업 코딩테스트에 나온 문제를 질문해주셔서 비슷한 로직으로 풀 수 있었다.

문제설명
1. 코드의 각 자리는 1부터 9까지의 자연수입니다.
2. 코드의 어떤 두 자리를 뽑아서 더해도 합이 9가 되지 않아야 합니다.

예를 들어, 세 자리 코드 119는 생성 가능하지만, 109는 0이 포함되므로 불가능, 217은 첫 번째 자리와 세 번째 자리의 합이 2+7=9가 되어 생성 불가능 합니다. 두 자리 코드의 경우, 11~99에서 18, 27, 36, 45, 54, 63, 72, 81을 제외한 9^2-8=73이 생성 가능한 코드의 경우의 수입니다.입력: 2<=N<=1,000,000인 N이 주어집니다.출력: 생성 가능한 N자리 코드의 경우의 수를 1000000007으로 나눈 나머지를 출력합니다.

import sys
input=sys.stdin.readline

N=int(input())
#DP [몇자리 수인지][비트마스크]=해당숫자들 나열
#DP는 0부터 9중 뭘 썼는지 파악하기 위해서 사용한다.
#0000000010 은 1만 쓴 거임 ex. 1, 11, 111 등 
DP=[[[] for _ in range(1024)] for _ in range(N+1)]
for i in range(1,10):
    DP[1][1<<i].append(i)

for i in range(2,N+1): #N=1일 때 N=2일 때 .. 쭉쭉 해결해보자
    for j in range(1024): #비트마스킹
        for k in DP[i-1][j]: #DP안에 들어있는 애들과
            #각 자리수에 1부터 9까지 붙여본다.
            for l in range(1,10):
                if j&(1<<(9-l))==0:
                    DP[i][j|(1<<l)].append(k*10+l)
print(DP)
ans=[]
for i in range(1024):
    ans.extend(DP[N][i])
print(ans)
print(len(ans))

사실 위 문제는 코드의 자리가 0부터 시작되지 않아서 조금 쉽다 (??)
비트마스킹 안 쓰고 그냥 점화식으로 풀어도 되는 문제이다.