[파이썬] 백준 1301 : 비즈 공예 (골드3)

[파이썬] 백준 1301 : 비즈 공예 (골드3)

• https://www.acmicpc.net/problem/1301
  

---

풀이

방향성 생각

• 다차원 DP / DFS + DP
• 다차원 DP로 접근할 경우 5개의 구슬 색 + 이전 2개의 상태 : 7개의 상태 구분조건이 주어져서 list로 구현할 경우 편해보이지 않음.
• DFS + DP로 가능한 노드에 접근했을 경우 메모제이션 해주고, 필요없는 부분은 가지치기.
• list 대신 hash 사용.
• 출근기록, ABC처럼 정답 하나를 찾는게 아니라 카운팅 해줘아하므로 set 대신 dict으로 개수까지 저장

전체코드

N = int(input())
remains = [int(input()) for _ in range(N)]
dp = {}

def dfs(remains: list, a: int , b: int):

    # 현재 상태가 메모제이션 돼있으면 바로 불러오기.
    state = (*remains,a,b)
    if state in dp:
        return dp[state]

    # 구슬을 다 썼으면 완성
    if sum(remains) == 0:
        return 1

    # 현재 구슬 남아있고, 뒤에 두 개에 같은색깔 없으면 탐색
    answer = 0
    for x in range(N):
        if remains[x] and x!=a and x!=b:
            remains[x] -= 1
            answer += dfs(remains,b,x)
            remains[x] += 1

    # 개수 저장
    dp[state] = answer
    return answer

print(dfs(remains,-2,-1))

코멘트

• 개수 없이 set로만 하려다가 메모제이션이 잘못돼서 시간 초과.
• dict으로 바꾸고 통과