[백준] 2629번 - 양팔저울 (C++) 문제 및 풀이

문제) 백준 - 동적 계획법 - 양팔저울

https://www.acmicpc.net/problem/2629

2629번: 양팔저울

 

추의 인덱스와 한쪽 저울에 올린 무게를 memoization을 적용하여 동적 계획법을 진행합니다. 추를 올릴 경우, 추를 올리지 않을 경우, 반대쪽에 올릴 경우를 생각하여 해결합니다.

 

C++ 소스코드)

	void solve(int idx, int total) {
	if (idx > N) return;
	int& ret = cache[idx][total];
	if (ret != -1) return;
	cache[idx][total] = 1;
	solve(idx + 1, total + chu[idx]);
	solve(idx + 1, total);
	solve(idx + 1, abs(total - chu[idx]));
	return;
	}

view raw 2629.cpp hosted with ❤ by GitHub

 

Full Code)

https://github.com/Chocochip101/BOJ_Solution/blob/main/Problem%201000~4999/2629_%EC%96%91%ED%8C%94%EC%A0%80%EC%9A%B8.cpp

GitHub - Chocochip101/BOJ_Solution: BOJ Solutions