[Python] 백준 2629 양팔저울

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

2629번: 양팔저울

 

1. 접근 방법

 양팔 저울과 추를 활용하여 특정 무게를 확인할 수 있는지 묻는 문제인데, 추가 양쪽 모두 올라갈 수 있다. 그래서 추들을 한쪽에 올려서 가능한지 뿐만 아니라, 일부 추가 반대쪽에 올라가서 가능한 경우도 고려해야 한다.

 DP로 배낭문제 방식으로 접근했는데, 각 무게가 가능한지 저장, 이후 주어지는 무게 별로 확인하여 출력하는 방식으로 구성했다.  

---

2. 풀이 코드

🖥python 코드 링크 : https://github.com/mintropy/PS/tree/master/BAEKJOON/Python/2000/2600/2629.py

GitHub - mintropy/PS: 다양한 알고리즘 문제 풀이 저장소입니다.

📕코드 해설

def search(idx: int, weight: int) -> None:
    global N, weights, dp
    if idx > N or dp[idx][weight]:
        return
    dp[idx][weight] = True
    search(idx + 1, weight + weights[idx])
    search(idx + 1, abs(weight - weights[idx]))
    search(idx + 1, weight)


if __name__ == "__main__":
    N = II()
    weights = list(MIIS()) + [0]
    dp = [[False] * 40_001 for _ in range(31)]
    search(0, 0)

    X = II()
    target = list(MIIS())
    ans = " ".join(["Y" if dp[N][t] else "N" for t in target])
    print(ans)

 DP구성을 위한 부분과 나머지로 구성되어 있다. DP 탐색은 재귀함수로 구성했는데, for문으로만 구성하는 데는 구성의 한계가 있거나, 너무 많은 조건을 확인하는 등 문제가 있어 재귀로 구성했다. 전략은 DP [i][j]에 i번째까지 추를 사용했을 때 j무게가 가능한지 알아내는 방식이다.
 출력은 join메서드와 더불어 list conprehension을 활용했다.

---

3. 생각 정리

 코딩 인터뷰에서 마주쳤던 문제다. 당시 이 문제를 조합론 문제로 생각하여 접근했는데, 그렇게 접근하면서도 터무니없는 풀이라고 생각했다. 이번에 다시 마주치면서 해결방법을 고민했고, DP를 활용할 수 있겠다고 뒤늦게 깨달았다. 문제를 잘 해결한다는 건 어떤 것일까라는 고민도 하게 되었다.

 다양한 문제와 유형을 마주치며 해결하는 과정을 겪어보는수밖에 없다는 결론은 예전이나 지금이나 크게 다르지 않은 것 같다.