[백준] 1301 비즈 공예 🌟

문제

• N개 종류의 구슬을 임의의 연속된 3개의 구슬 색이 모두 다르게 나열할 때 가능한 경우의 수는?
  • 3 <= N <= 5
• 가지고 있는 구슬을 모두 사용해야 한다.
  • (구슬 개수) <= 10
  • 3 <= (총 구슬 개수) <= 35

 

풀이 1

• 완전 탐색
• q에 현재 가능한 모든 경우의 수를 넣어서 개수 세면 되지 않을까?
• 시간 복잡도 계산이 잘 안돼서 일단 시도.
• 역시나.. 시간초과!

from collections import deque

N = int(input())    # 구슬 종류
# 구슬 별 개수 입력 받기
beads = []
for _ in range(N):
    beads.append(int(input()))

# 2개 구슬 까지의 경우의 수 큐에 넣기
q = deque()
for i in range(N):
    for j in range(N):
        if i == j : continue
        beads[i] -= 1
        beads[j] -= 1
        q.append(([i, j], beads[:]))
        beads[i] += 1
        beads[j] += 1

all_beads = sum(beads)  # 전체 구슬 개수
cnt = 0                 # 가능한 경우의 수
while q:
    now, beads = q.popleft()

    if len(now) == all_beads:   # 구슬 목걸이 완성~
        cnt += 1

    impossible = set([now[-1], now[-2]])    # 넣으면 안되는 두 가지 색상
    for i in range(N):
        if i in impossible : continue       # 제외하고  
        if beads[i] == 0 : continue         # 구슬없으면 제외하고
        beads[i] -= 1
        q.appendleft((now+[i], beads[:]))       # 경우의 수 추가 하기
        beads[i] += 1
    
print(cnt)

 

 

풀이 2

• DP
• 중복된 경우의 수를 줄여야 시간초과를 통과한다.
  • 1번~5번 구슬의 개수와 이전 구슬, 전전 구슬 번호를 기록하는 7차원 리스트를 만들어 기록

import sys
from collections import deque
sys.setrecursionlimit(10**4)	# 재귀 제한 풀기 

N = int(input())    # 구슬 종류
# 구슬 별 개수 입력 받기
beads = [0] * 6
for i in range(1, N+1):
    beads[i] = int(input())

# dp[1번 구슬 개수][2번 구슬 개수]...[5번구슬 개수][이전 구슬 번호][전전 구슬 번호]
dp = [[[[[[ [-1]*6 for _ in range(6)] for _ in range(11)] 
             for _ in range(11)] for _ in range(11)]
             for _ in range(11)] for _ in range(11)] 
            
def counting(beads, before, before_before):	# (구슬, 이전 구슬 번호, 전전 구슬 번호)
    # 모든 구슬 사용한 경우, count +1
    if beads[1] == beads[2] == beads[3] == beads[4] == beads[5] == 0:
        return 1
    
    # 이미 처리한 적이 있는 경우는 그대로 리턴
    _, one, two, three, four, five = beads
    now = dp[one][two][three][four][five][before][before_before]
    if now != -1 :
        return now
    
    # 경우의 수 세기
    now = 0
    for i in range(1, 6):	
    	# i번째 구슬이 1개 이상이고 이전 구슬과 전전 구슬이 i번이 아니라면,
        if beads[i] >= 1 and before != i and before_before != i:
            beads[i] -= 1					# i 번 구슬 사용
            cnt = dfs(beads[:], i, before)	# ...(전전)(전)(i) 가 됨
            now += cnt		
            # 현재 패턴의 개수 기록하기
            _, one, two, three, four, five = beads
            dp[one][two][three][four][five][i][before] = cnt
            beads[i] += 1					# i 번 구슬 사용 전으로 돌리기
            
    return now

print(counting(beads, -1 , -1))

 

References

• 백준 1301번
• 2023.04.24 오늘의 문제