2629 양팔저울
-
백준 2629 양팔저울Algorithm/BOJ 2021. 4. 8. 18:29
출처: www.acmicpc.net/problem/2629 분류: DP 접근방식 DFS 느낌으로 무게를 달 수 있는 경우들을 잘 세어야 하는 문제였습니다. 하나의 추를 놓고 3가지 경우를 생각해볼 수 있습니다. 1. 추를 추가하지 않았을 경우 2. 추를 구슬 반대쪽에 추가 ( weight + 추 ) 3. 추를 구슬 쪽에 추가 ( |weight - 추| ) 문제는 기저사례를 체크하는 부분이었는데, 단순히 무게만으로 확인했는지 체크하면 안 됩니다. 추를 몇 개를 사용했는지에 따라서 다음 무게들이 달라질 수 있기 때문에 몇 개의 추를 사용해 만든 무게인지 구분해줘야 합니다. 따라서 [현재 추][무게] 인 2차원 배열로 체크해줬네요! 추를 추가하지 않는 경우도 생각해줬기 때문에 마지막에 체크해줄 때는 추를 모두..