[백준] 2629번(python 파이썬) - 양팔저울

문제 링크: https://www.acmicpc.net/problem/2629

2629번: 양팔저울

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	128 MB	18459	5732	4139	31.905%

문제

양팔 저울과 몇 개의 추가 주어졌을 때, 이를 이용하여 입력으로 주어진 구슬의 무게를 확인할 수 있는지를 결정하려고 한다.

무게가 각각 1g과 4g인 두 개의 추가 있을 경우, 주어진 구슬과 1g 추 하나를 양팔 저울의 양쪽에 각각 올려놓아 수평을 이루면 구슬의 무게는 1g이다. 또 다른 구슬이 4g인지를 확인하려면 1g 추 대신 4g 추를 올려놓으면 된다.

구슬이 3g인 경우 아래 <그림 1>과 같이 구슬과 추를 올려놓으면 양팔 저울이 수평을 이루게 된다. 따라서 각각 1g과 4g인 추가 하나씩 있을 경우 주어진 구슬이 3g인지도 확인해 볼 수 있다.

<그림 1> 구슬이 3g인지 확인하는 방법 (1$\boxed{1}$은 1g인 추, 4$\boxed{4}$는 4g인 추, ●은 무게를 확인할 구슬)

<그림 2>와 같은 방법을 사용하면 구슬이 5g인지도 확인할 수 있다. 구슬이 2g이면 주어진 추를 가지고는 확인할 수 없다.

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

<그림 2> 구슬이 5g인지 확인하는 방법

입력

첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30 이하이다. 둘째 줄에는 추의 무게들이 자연수로 가벼운 것부터 차례로 주어진다. 같은 무게의 추가 여러 개 있을 수도 있다. 추의 무게는 500g이하이며, 입력되는 무게들 사이에는 빈칸이 하나씩 있다. 세 번째 줄에는 무게를 확인하고자 하는 구슬들의 개수가 주어진다. 확인할 구슬의 개수는 7이하이다. 네 번째 줄에는 확인하고자 하는 구슬들의 무게가 자연수로 주어지며, 입력되는 무게들 사이에는 빈 칸이 하나씩 있다. 확인하고자 하는 구슬의 무게는 40,000보다 작거나 같은 자연수이다.

출력

주어진 각 구슬의 무게에 대하여 확인이 가능하면 Y, 아니면 N 을 차례로 출력한다. 출력은 한 개의 줄로 이루어지며, 각 구슬에 대한 답 사이에는 빈칸을 하나씩 둔다.

 

 

 

 

 

 

풀이

---

이 문제는 dp를 이용해야하는 문제이다. 

처음에 브루트 포스 알고리즘을 생각하고 시간복잡도를 구해보면 O(3**n)이 나온다. (n은 추의 개수)

-> 추를 놓을 수 있는 경우의 수가 3가지이기 때문이다.

1. 추를 왼쪽에 올려놓는다.

2. 추를 놓지 않는다.

3. 추를 오른쪽에 올려놓는다. 

 

근데 dp를 어떻게 활용해야할지 감이 잘 오지 않았다. 

여기서 배낭문제 알고리즘을 찾아봤는데 기존에 써봤던 dp방법하고 조금 달랐다. 

 

기존의 dp는 고려해야할 부분이 최댓값만 고려하면 되는 느낌이었다면

배냥알고리즘은 조건이 더 붙어도 풀 수 있도록 만들어진 알고리즘 같았다.

 

배낭문제 알고리즘을 문제에 적용해보자

일단 문제상황은 다음과 같이 3가지로 나뉠 수 있다.

1. 추를 왼쪽에 올려놓는다.

2. 추를 놓지 않는다.

3. 추를 오른쪽에 올려놓는다. 

 

이렇게 코드를 구현하면 시간복잡도는 역시 O(n^3)이다. 

 

어떻게 시간복잡도를 줄여야 할까..?( 맞춰볼 사람 구함)

 

 

 

 

 

 

 

 

 

 

 

???: 중복을 제거하면 됩니다!

 

 

(나 혼자 뭐하냐......  현자타임)

ㅋㅋㅋㅋㅋ

 

 

 

 

자 10 20 30 40 50 의 추가 있다고 생각해보자

20 / 40 이 있는 경우는 양쪽의 차이가 20이다. -> 무게 20인 구슬의 무게 구할 수 있음

10 / 30 이 있는 경우는 역시 양쪽의 차이가 20이다. -> 무게 20인 구슬의 무게 구할 수 있음

 

여기서 양쪽 저울의 무게차이가 같고 추의 리스트에서 탐색한 index의 수가 같으면 중복된 경우이다.

-> 남은 추의 무게를 저장한 list는 같고 양쪽 무게 차이도 같기 때문이다. 

-> 이 부분은 진행을 안해도 된다.

 

방문록을 dp list로 만들어보자 -> dp[사용한 추의 개수][추의 무게 차이]

 

dp 초기화를 다음과 같이 할 수 있다. 

dp = [[0 for _ in range((500 * j)+1)] for j in range(n+1)]

 추의 최대무게가 500이고 추의 개수는 n이다.

 

그리고 재귀를 이용해서 방문한 dp list가 1이면 return을 해줘서 중복을 제거해준다.

(물론 0이 미방문)

 

 

 

그리고 저울의 반대쪽에 놓는 추의 무게 계산은 abs함수를 이용해서 절댓값계산을 했다.

(무게가 -가 나올수는 없기 때문)

 

 이 재귀함수를 cal이라고 하자.

cal함수가 모두 진행된다면 dp 리스트에는 측정가능한 구슬의 무게에 dp[n][구슬의 무게] == 1이 성립할것이다.

  

 

그렇다면 구슬무게 리스트에 for문을 적용해 dp[n][구슬의 무게] == 1에 해당하면 정답 아니면 오답처리를 하면된다.

 

만하면 끝날줄 알았지만 구슬의 무게가 추의 무게를 초과하는 경우가 발생할 수 있다.

(500 * n이 40000보다 작을 수 있기 때문)

 

그래서 index에러가 발생했다. ㅜㅜ 

 

역시 문제를 잘 읽어야한다. 

 

이상 글 마침!

 

구현 코드

---

from sys import stdin
input = stdin.readline

n, w = int(input()), list(map(int, input().split()))
m, b = int(input()), list(map(int, input().split()))


# 추의 최대 무게 500 추의 개수 n
dp = [[0 for _ in range((500 * j)+1)] for j in range(n+1)]
ans = []

def cal(num, weight): # 추로 판별할 수 있는 구슬의 무게를 나타내는 함수
    if num > n: # 구슬의 숫자가 주어진 구슬보다 크다면 return
        return
    if dp[num][weight] == 1: # 이미 같은 추의 무게와 개수로 방문했다면 return
        return
    dp[num][weight] = 1

    cal(num+1, weight + w[num-1])# 추 넣기
    cal(num+1, weight)# 추 그대로 진행
    cal(num+1, abs(weight - w[num-1]))# 추 다른쪽에 넣기 (무게빼기)

cal(0, 0)

for bead in b:
    if bead > 500 * n:
        ans.append('N')
    elif dp[n][bead] == 1:
        ans.append('Y')
    else:
        ans.append('N')

print(*ans)