[백준/c++] 2629번 - 양팔저울

[ 문제 ]

 

[ 구현 ]

dp[cnt][total] : cnt번째까지의 추를 통해 total의 무게를 만들 수 있는가를 기록하는 배열

 

solve(cnt + 1, abs(total - w[cnt]));
solve(cnt + 1, total);
solve(cnt + 1, total + w[cnt]);

와 같이 재귀적으로 해당 추를 통해 무게를 더할지, 뺄지, 사용하지 않을지를 반영해주며 배열에 기록해나간다.

 

종료조건은 cnt>n으로 설정해주고,

이미 이전에 방문한 적이 있는 cnt와 total의 경우에 도달한 경우 곧바로 탈출하여 중복으로 탐색하는 것을 막아주어야만 시간 초과가 나지 않는다.

 

[ 코드 ]

 

#include <iostream>
#include <cmath>

using namespace std;

int n;
int dp[31][15001];
int w[31];
int check_num;

void solve(int cnt, int total) {
	if (cnt > n || dp[cnt][total]) return;

	dp[cnt][total] = 1;

	solve(cnt + 1, abs(total - w[cnt]));
	solve(cnt + 1, total);
	solve(cnt + 1, total + w[cnt]);

}

int main() {
	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> w[i];
	}

	solve(0, 0);

	cin >> check_num;

	for (int i = 1; i <= check_num; i++) {
		int x;
		cin >> x;

		if (x > 15000) {
			cout << "N ";
			continue;
		}
		bool check = false;

		for (int j = 1; j <= n; j++) {
			if (dp[j][x]) check = true;
		}

		if (check) cout << "Y ";
		else cout << "N ";
	}

	return 0;
}








int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> n;

	dq(0, n - 1, 0);

	for (int i = 0; i < print_cnt; i++) {
		for (int j = 0; j < n; j++) {
			if (arr[i][j] == '\0') {
				arr[i][j] = 'A';
			}
		cout << arr[i][j];
		}
		cout << '\n';
	}

	while (print_cnt < 7) {
		cout << 'A';

		for (int i = 1; i < n; i++) {
			cout << 'B';
		}

		cout << '\n';

		print_cnt++;
	}
	return 0;
}

 

 

 

[ 마무리 및 느낀 점 ]

 

메모이제이션+재귀의 느낌으로 푸는 문제였다.

그렇게 어렵지는 않으나 처음에 배열의 크기를 이렇게 크게 잡고 돌려도 시간 초과가 나지 않을까 하는 의문에 헤맸다.

문제를 좀 더 꼼꼼히 읽어서 틀을 확실하게 잡고 풀기 시작하도록 해야겠다.