난이도 : 골드 3
유형 : DP 심화
https://www.acmicpc.net/problem/2629

문제 접근

문제가 원하는 것 :
추들의 무게와 확인할 구슬들의 무게가 입력되었을 때, 주어진 추만을 사용하여 구슬의 무게를 확인 할 수 있는지를 결정하는 프로그램을 작성하시오.

첫째 줄에 추의 개수 N 입력받는다. N은 30이하

둘째 줄에 추의 무게들 공백을 기준으로 자연수로 입력받음 ( 가벼운 것부터 , 중복 가능 , 무게 500 이하)

셋째 줄에 확인하고자 하는 무게의 개수 M 입력받는다.

넷째 줄에 확인하고자 하는 무게 M개 입력받는다. 자연수로 , 공백을 기준으로 40,000보다 작거나 같다.

각 무게에 대해 확인 가능하면 Y, 불가능하면 N

---

• 무게추를 왼쪽/오른쪽/사용하지 않음 세 가지 방식으로 배치할 수 있음
• 목표: 구슬의 무게를 측정할 수 있는지 판단 (무게추 조합으로)
• 가능한 모든 무게 조합을 탐색하면서, 해당 무게를 만들 수 있는지를 체크하는 DP + DFS 문제

핵심 아이디어

• DFS로 가능한 모든 무게 차이를 탐색
• 상태: 현재 추 인덱스, 현재 무게 차이
• 메모이제이션으로 이미 탐색한 (index, weight)는 다시 탐색하지 않음 → 중복 제거
• 최종적으로 만들 수 있는 무게들을 체크해두고, 질문에 대해 'Y' or 'N' 출력

dfs(index, weight)
→ index번째 추까지 사용해서
→ 무게 차이 weight를 만들 수 있는가?

각 추를 볼 때마다 우리는 세 가지 선택을 할 수 있다:

선택	동작	결과 무게
왼쪽에 놓는다	weight + 추	무게 증가
오른쪽에 놓는다	abs(weight - 추)	무게 보정
안 쓴다	weight 그대로	영향 없음

즉, 추를 하나 볼 때마다 3갈래로 분기되는 DFS 탐색 트리가 만들어진다.

중복 제거 = 메모이제이션
이미 dp[index][weight] == True라면 → 다시 방문하지 않음

→ 그래서 결국 모든 가능한 무게 차이를 dp[n][무게] = True로 기록해두고,
→ 구슬 무게가 그 안에 있으면 측정 가능 한 꼴

dfs(0, 0)에서 출발

각 추마다 3갈래 길로 뻗어 나가면서 도달할 수 있는 모든 무게 지점을 찍음

지도 완성 후, 구슬 무게가 그 지점 안에 있으면 Y, 아니면 N

해답 및 풀이

import sys
input = sys.stdin.readline

N = int(input())
weights = list(map(int,input().split()))
M = int(input())
balls = list(map(int,input().split()))

MAX = 40000 # 최대 가능한 무

# dp[i][w] = True는 앞에서부터 i개의 추를 이용해 무게 w를 만들 수 있다는 의미
dp = [[False] * (MAX + 1) for _ in range(N+1)]

def dfs(index, weight):
    if index > N or dp[index][weight]:
        return
    dp[index][weight] = True # 방문한 것으로 처리

    if index < N:

        # 추를 왼쪽에 놓는 경우
        dfs(index + 1, weight + weights[index])
        # 추를 오른쪽에 놓는 경우
        dfs(index +1, abs(weight - weights[index]))
        # 추를 사용하지 않는 경우
        dfs(index + 1, weight)

dfs(0,0)

for ball in balls:
    print('Y' if dp[N][ball] else 'N', end=' ')