Go, Vantage point
가까운 곳을 걷지 않고 서는 먼 곳을 갈 수 없다.
Github | https://github.com/overnew/
Blog | https://everenew.tistory.com/
티스토리 뷰
문제
https://www.acmicpc.net/problem/2629
2629번: 양팔저울
첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30 이하이다. 둘째 줄에는 추의 무게들이 자연수로 가벼운 것부터 차례로 주어진다. 같은 무게의 추가 여러 개 있을 수도 있다. 추의 무
www.acmicpc.net
풀이
DP문제 중에서도 배낭 문제에 해당한다.
배낭 알고리즘은 특정 조건을 만족시키는 물건을 선택하는 조합을 구해낼 수 있다.
해당 문제에서 구슬의 무게를 알 수 있는 경우는 두 가지이다.
1. 구슬 VS 추가 평형을 이루는 경우
2. 구슬+추 VS 추가 평형을 이루는 경우
1번의 경우 단순히 현재 weight에서 idx 번째 추를 선택하거나 선택하지 않는 경우를 확인하는 점화식을 거치면 된다.
dp[weight][idx] = dp[weight - idx추의 무게][idx-1] || dp[weight][idx-1]
dp의 weight가 0인 경우만 모두 true 로 설정 해두고
idx는 모두 idx-1 번째 추로 넘어가 해당 추를 선택하거나 하지않는 경우의 탐색을 계속 진행한다.
최종적으로는 해당 무게(weight)를 추들의 조합을 만들수 있는 지의 여부는 dp[weight][weight_num]로 확인이 가능하다.
2번의 경우는 구슬의 무게 + 추의 무게 조합 = 추의 무게 조합 인 경우 해당 구슬의 무게를 확인이 가능하다.
따라서 모든 weight를 순회하면서, dp[weight][weight_num] 과 dp[weight+구슬의 무게][weight_num]가 모두 true인 경우를 확인하면 된다.
마지막으로 1,2번 중 한가지라도 true인 경우 Y를 출력해준다.
코드
'알고리즘 공부 > 백준' 카테고리의 다른 글
| [백준] No.10942 - 팰린드롬? (C++) (0) | 2020.12.06 |
|---|---|
| [백준] No.2482 - 색상환 (C++) (0) | 2020.12.02 |
| [백준] No.12865 - 평범한 배낭 (C++, 배낭 문제) (0) | 2020.12.01 |
| [백준] No.10835 - 카드게임 (C++) (0) | 2020.11.29 |
| [백준] No.2491 - 수열 (C++) (0) | 2020.11.29 |