ABC_080_C - Shopping Street

[zeikar]

Problem link

https://atcoder.jp/contests/abc080/tasks/abc080_c

Problem Summary

상점을 오픈하는데, 특정 시간에 다른 상점이 열린 개수에 따라 최대로 만들 수 있는 이익을 구하는 문제.
Fij : i 상점이 j 시간에 열려 있는지 여부.
Pij : i 상점이 j 시간만큼 열린 시간이 겹쳤을 때 얻을 수 있는 이익.

Solution

처음에 문제 자체를 이해하기 좀 어려웠는데 계속 보니까 대략 머리에 들어왔다.

일단, Joisino가 상점을 열지 말지 두 가지 방법이 있고 시간이 총 10개 있으므로 단순 2^10 탐색을 해주면 된다.

상점을 열었을 경우 그 시점에 다른 상점이 열려있는 개수를 카운트 하고 더해주면 되는 간단한 문제.

Source Code

#include <iostream>
using namespace std;

int f[100][10];
int p[100][11];

int main() {
	int n;
	cin >> n;

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

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

	int ans = -1987654321;
	for (int i = 1; i < (1 << 10); i++)
	{
		int profit = 0;

		for (int j = 0; j < n; j++)
		{
			int cnt = 0;

			for (int k = 0; k < 10; k++)
			{
				// open
				if (i & (1 << k) && f[j][k] == 1)
				{
					cnt++;
				}
			}

			profit += p[j][cnt];
		}

		ans = max(ans, profit);
	}

	cout << ans << endl;
}