Bin_S+StudyRoom

• 문제

상근이는 문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다.

폭발은 다음과 같은 과정으로 진행된다.

• 문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다.
• 새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다.
• 폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다.

상근이는 모든 폭발이 끝난 후에 어떤 문자열이 남는지 구해보려고 한다. 남아있는 문자가 없는 경우가 있다. 이때는 "FRULA"를 출력한다.

폭발 문자열은 같은 문자를 두 개 이상 포함하지 않는다.

• 입력

첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다.

둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다.

두 문자열은 모두 알파벳 소문자와 대문자, 숫자 0, 1, ..., 9로만 이루어져 있다.

• 출력

첫째 줄에 모든 폭발이 끝난 후 남은 문자열을 출력한다.

• 예제 입력

mirkovC4nizCC44
C4

12ab112ab2ab
12ab

• 예제 출력

mirkovniz

FRULA

• 접근방식

폭발, 짝짓기 라는 단어가 나오면 stack을 이용해서 풀 수 있다.

입력 받은 문자열 하나씩 스택에 넣고 스택의 크기가 폭발 문자열의 크기보다 크거나 같다면 스택의 상단 부분과 폭발 문자열 끝 부분을 비교해서 그것도 같다면 빈 문자열에 폭발 문자열의 크기만큼 스택을 빼서 넣고 비교한다. 즉, 다시 말하자면

1. 입력 받은 문자열을 전부 순회하면서 하나씩 스택에 넣기
2. 순회하면서 스택의 크기가 폭발 문자열의 크기보다 크거나 같다면
3. 스택 상단 부분과 폭발 문자열 끝 부분을 비교해서 같다면
4. 빈 문자열에 폭발 문자열의 크기만큼 스택을 빼서 넣고 비교(스택에서 빼온 부분은 반대로 되어 있어서 뒤집어 줘야함)
5. 만약 폭발 문자열이 아니면 다시 스택에 넣어주기
6. 만약 폭발 문자열이라면 스택에 다시 넣지 않고 다시 순회하기
7. 순회가 끝나고 스택이 비어있으면 FRULA 출력, 아니라면 결과 문자열에 스택의 윗부분 하나씩 빼고 뒤집기

stack 말고도 erase를 사용해서 풀 수 있다.

1. 입력 받은 문자열을 전부 순회하면서 결과 문자열에 붙힘
2.순회하면서 결과 문자열의 크기가 폭발 문자열의 크기보다 크거나 같으면
3. 결과 문자열의 크기 - 폭발 문자열의 크기 ~ 폭발 문자열의 크기까지가 폭발 문자열과 같다면 (즉, 끝에 폭발 문자열의 크기만큼의 자리)
4. 해당 부분을 제거하면서 순회
5. 순회가 끝나고 결과 문자열이 비어있으면 FRULA출력, 아니라면 결과 문자열 출력

• 코드

#include <iostream>
#include <algorithm>
#include <stack>

using namespace std;

string s, bomb, result;
stack<char> stk;

int main()
{
    cin >> s >> bomb;

    for (char a : s)
    {
        stk.push(a);
        if (stk.size() >= bomb.size() && stk.top() == bomb[bomb.size() - 1]) // 스택의 크기와 폭발 문자열 크기를 비교후 스택의 상단 부분과 폭발 문자열 끝 부분 비교
        {
            string temp = "";
            for (char i : bomb)
            {
                temp += stk.top();
                stk.pop();
            }
            reverse(temp.begin(), temp.end()); // 스택에서 빼온 부분은 반대로 되어 있기 때문에 다시 뒤집기
            if (bomb != temp) // 폭발 문자열이 아니면 다시 집어넣기
            {
                for (char i : temp)
                {
                    stk.push(i);
                }
            }
        }
    }

    if (!stk.size())
    {
        cout << "FRULA";
    }
    else
    {
        while (stk.size())
        {
            result += stk.top();
            stk.pop();
        }
        reverse(result.begin(), result.end());
        cout << result;
    }

    return 0;
}

#include <iostream>
#include <algorithm>

using namespace std;

string s, bomb, result;

int main()
{
    cin >> s >> bomb;

    for (char a : s)
    {
        result += a;
        if (result.size() >= bomb.size() && result.substr(result.size() - bomb.size(), bomb.size()) == bomb)
        {
            result.erase(result.end() - bomb.size(), result.end());
        }
    }

    if (!result.size())
    {
        cout << "FRULA";
    }
    else
    {
        cout << result;
    }
    return 0;
}

• 문제링크 : https://www.acmicpc.net/problem/9935

• 문제

한 저명한 학자에게 n(0 ≤ n ≤ 10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불하겠다고 알려왔다. 각 대학에서 제시하는 d와 p값은 서로 다를 수도 있다. 이 학자는 이를 바탕으로, 가장 많은 돈을 벌 수 있도록 순회강연을 하려 한다. 강연의 특성상, 이 학자는 하루에 최대 한 곳에서만 강연을 할 수 있다.

예를 들어 네 대학에서 제시한 p값이 각각 50, 10, 20, 30이고, d값이 차례로 2, 1, 2, 1 이라고 하자. 이럴 때에는 첫째 날에 4번 대학에서 강연을 하고, 둘째 날에 1번 대학에서 강연을 하면 80만큼의 돈을 벌 수 있다.

• 입력

첫째 줄에 정수 n이 주어진다. 다음 n개의 줄에는 각 대학에서 제시한 p값과 d값이 주어진다.

• 출력

첫째 줄에 최대로 벌 수 있는 돈을 출력한다.

• 예제 입력

7
20 1
2 1
10 3
100 2
8 2
5 20
50 10

• 예제 출력

185

• 접근방식

그리디 문제로 그리디는 Sort 아니면 PQ(Priority queue = 우선순위 큐)를 쓰거나 둘을 동시에 사용한다.

해당 문제는 오름 차순 정렬후, PQ에서 최소를 빼는 식으로 계산한다.

• 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

int n, p, d, result;
vector<pair<int, int>> v;
priority_queue<int, vector<int>, greater<int>> pq;

int main()
{
    cin >> n;

    for (int i = 0; i < n; i++)
    {
        cin >> p >> d;
        v.push_back({ d, p });
    }

    sort(v.begin(), v.end());

    for (int i = 0; i < n; i++)
    {
        pq.push(v[i].second);
        if (pq.size() > v[i].first) // 오름 차순으로 정렬되어 있어서 1일차, 2일차 이런식으로 비교
        {
            pq.pop();
        }
    }

    while (pq.size())
    {
        result += pq.top();
        pq.pop();
    }

    cout << result;
    return 0;
}

• 문제링크 : https://www.acmicpc.net/problem/2109

• 문제

백준시의 시장 최백준은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 최백준은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름도 백준시로 변경했다. 이번 선거에서는 최대한 공평하게 선거구를 획정하려고 한다.

백준시는 N개의 구역으로 나누어져 있고, 구역은 1번부터 N번까지 번호가 매겨져 있다. 구역을 두 개의 선거구로 나눠야 하고, 각 구역은 두 선거구 중 하나에 포함되어야 한다. 선거구는 구역을 적어도 하나 포함해야 하고, 한 선거구에 포함되어 있는 구역은 모두 연결되어 있어야 한다. 구역 A에서 인접한 구역을 통해서 구역 B로 갈 수 있을 때, 두 구역은 연결되어 있다고 한다. 중간에 통하는 인접한 구역은 0개 이상이어야 하고, 모두 같은 선거구에 포함된 구역이어야 한다.

아래 그림은 6개의 구역이 있는 것이고, 인접한 구역은 선으로 연결되어 있다.

아래는 백준시를 두 선거구로 나눈 4가지 방법이며, 가능한 방법과 불가능한 방법에 대한 예시이다.

공평하게 선거구를 나누기 위해 두 선거구에 포함된 인구의 차이를 최소로 하려고 한다. 백준시의 정보가 주어졌을 때, 인구 차이의 최솟값을 구해보자.

• 입력

첫째 줄에 구역의 개수 N이 주어진다. 둘째 줄에 구역의 인구가 1번 구역부터 N번 구역까지 순서대로 주어진다. 인구는 공백으로 구분되어져 있다.

셋째 줄부터 N개의 줄에 각 구역과 인접한 구역의 정보가 주어진다. 각 정보의 첫 번째 정수는 그 구역과 인접한 구역의 수이고, 이후 인접한 구역의 번호가 주어진다. 모든 값은 정수로 구분되어져 있다.

구역 A가 구역 B와 인접하면 구역 B도 구역 A와 인접하다. 인접한 구역이 없을 수도 있다.

• 출력

첫째 줄에 백준시를 두 선거구로 나누었을 때, 두 선거구의 인구 차이의 최솟값을 출력한다. 두 선거구로 나눌 수 없는 경우에는 -1을 출력한다.

• 예제 입력

6
5 2 3 4 1 2
2 2 4
4 1 3 6 5
2 4 2
2 1 3
1 2
1 2

6
1 1 1 1 1 1
2 2 4
4 1 3 6 5
2 4 2
2 1 3
1 2
1 2

6
10 20 10 20 30 40
0
0
0
0
0
0

6
2 3 4 5 6 7
2 2 3
2 1 3
2 1 2
2 5 6
2 4 6
2 4 5

• 예제 출력

1

0

-1

9

• 접근방식

색을 2개로 나눠서 칠한다. 즉, 0또는 1로 설정하는데 2개로 나눠서 경우의 수를 구하면 된다. > 비트 마스킹을 이용하여 푸는데 dfs를 시켜줘야함 > pair로 쌍을 나누어 진행

• 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>

using namespace std;

int n, a[11], m, temp, comp[11], visited[11], result = 99999999;
vector<int> adj[11];

pair<int, int> dfs(int here, int value)
{
	visited[here] = 1;
	pair<int, int> result = { 1,a[here] };
	for (int there : adj[here])
	{
		if (comp[there] != value || visited[there])		continue;
		pair<int, int> _temp = dfs(there, value);
		result.first += _temp.first;
		result.second += _temp.second;
	}
	return result;
}

int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
	}

	for (int i = 1; i <= n; i++)
	{
		cin >> m;
		for (int j = 0; j < m; j++)
		{
			cin >> temp;
			adj[i].push_back(temp);
			adj[temp].push_back(i);
		}
	}
	for (int i = 1; i < (1 << n) - 1; i++)
	{
		fill(comp, comp + 11, 0);
		fill(visited, visited + 11, 0);
		int idx1 = -1, idx2 = -1;
		for (int j = 0; j < n; j++)
		{
			if (i & (1 << j))
			{
				comp[j + 1] = 1;
				idx1 = j + 1;
			}
			else
			{
				idx2 = j + 1;
			}
		}
		pair<int, int> comp1 = dfs(idx1, 1);
		pair<int, int> comp2 = dfs(idx2, 0);
		if (comp1.first + comp2.first == n)
		{
			result = min(result, abs(comp1.second - comp2.second));
		}
	}
	cout << (result == 99999999 ? -1 : result);
    return 0;
}

• 문제링크 : https://www.acmicpc.net/problem/17471

• 문제

N^2개의 동전이 N행 N열을 이루어 탁자 위에 놓여 있다. 그 중 일부는 앞면(H)이 위를 향하도록 놓여 있고, 나머지는 뒷면(T)이 위를 향하도록 놓여 있다. <그림 1>은 N이 3일 때의 예이다.

이들 N^2개의 동전에 대하여 임의의 한 행 또는 한 열에 놓인 N개의 동전을 모두 뒤집는 작업을 수행할 수 있다. 예를 들어 <그림 1>의 상태에서 첫 번째 열에 놓인 동전을 모두 뒤집으면 <그림 2>와 같이 되고, <그림 2>의 상태에서 첫 번째 행에 놓인 동전을 모두 뒤집으면 <그림 3>과 같이 된다.

<그림 3>의 상태에서 뒷면이 위를 향하여 놓인 동전의 개수는 두 개이다. <그림 1>의 상태에서 이와 같이 한 행 또는 한 열에 놓인 N개의 동전을 모두 뒤집는 작업을 계속 수행할 때 뒷면이 위를 향하도록 놓인 동전의 개수를 2개보다 작게 만들 수는 없다.

N^2개의 동전들의 초기 상태가 주어질 때, 한 행 또는 한 열에 놓인 N개의 동전을 모두 뒤집는 작업들을 수행하여 뒷면이 위를 향하는 동전 개수를 최소로 하려 한다. 이때의 최소 개수를 구하는 프로그램을 작성하시오.

• 입력

첫째 줄에 20이하의 자연수 N이 주어진다. 둘째 줄부터 N줄에 걸쳐 N개씩 동전들의 초기 상태가 주어진다. 각 줄에는 한 행에 놓인 N개의 동전의 상태가 왼쪽부터 차례대로 주어지는데, 앞면이 위를 향하도록 놓인 경우 H, 뒷면이 위를 향하도록 놓인 경우 T로 표시되며 이들 사이에 공백은 없다.

• 출력

첫째 줄에 한 행 또는 한 열에 놓인 N개의 동전을 모두 뒤집는 작업들을 수행하여 뒷면이 위를 향하여 놓일 수 있는 동전의 최소 개수를 출력한다.

• 예제 입력

3
HHT
THH
THT

• 예제 출력

2

• 접근방식

뒤집는다. > 비트마스킹의 '~' 생각

H를 0으로 T를 1로 보고 비트 마스킹을 통해서 풀어나간다. > 단, 뒤집을 때 (비트를 반전 시킬 때) 앞에 자리수는 생각하지 말 것 (3개만 보기)

• 코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int n, a[44], result = 99999999;
string s;

void flip(int here)
{
	if (here == n + 1)
	{
		int sum = 0;
		for (int i = 1; i <= (1 << (n - 1)); i *= 2)
		{
			int cnt = 0;
			for (int j = 1; j <= n; j++)
			{
				if (a[j] & i)	cnt++;
			}
			sum += min(cnt, n - cnt);
		}
		result = min(result, sum);
		return;
	}
	flip(here + 1);
	a[here] = ~a[here];
	flip(here + 1);
}

int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> s;
		int value = 1;
		for (int j = 0; j < s.length(); j++)
		{
			if (s[j] == 'T')
			{
				a[i] |= value;
			}
			value *= 2;
		}
	}
	flip(1);
	cout << result;
    return 0;
}

• 문제링크 : https://www.acmicpc.net/problem/1285

• 문제

식재료 N개 중에서 몇 개를 선택해서 이들의 영양분(단백질, 탄수화물, 지방, 비타민)이 일정 이상이 되어야 한다. 아래 표에 제시된 6가지의 식재료 중에서 몇 개를 선택해서 이들의 영양분의 각각 합이 최소 100, 70, 90, 10가 되도록 하는 경우를 생각해보자. 이 경우 모든 재료를 선택하면 쉽게 해결되지만, 우리는 조건을 만족시키면서도 비용이 최소가 되는 선택을 하려고 한다.

예를 들어, 식재료 1, 3, 5를 선택하면 영양분은 100, 145, 130, 10으로 조건을 만족하지만 가격은 270이 된다. 대신 2, 3, 4를 선택하면 영양분의 합은 110, 130, 90, 10, 비용은 180이 되므로, 앞의 방법보다는 더 나은 선택이 된다.

입력으로 식재료 표가 주어졌을 때, 최저 영양소 기준을 만족하는 최소 비용의 식재료 집합을 찾아야 한다.

• 입력

첫 줄에 식재료의 개수 N이 주어진다.

다음 줄에는 단백질, 지방, 탄수화물, 비타민의 최소 영양성분을 나타내는 정수 mp, mf, ms, mv가 주어진다.

이어지는 N개의 각 줄에는 i번째 식재료의 단백질, 지방, 탄수화물, 비타민과 가격이 5개의 정수 p_i, f_i, s_i, v_i, c_i와 같이 주어진다. 식재료의 번호는 1부터 시작한다.

• 출력

첫 번째 줄에 최소 비용을 출력하고, 두 번째 줄에 조건을 만족하는 최소 비용 식재료의 번호를 공백으로 구분해 오름차순으로 한 줄에 출력한다. 같은 비용의 집합이 하나 이상이면 사전 순으로 가장 빠른 것을 출력한다.

조건을 만족하는 답이 없다면 -1을 출력하고, 둘째 줄에 아무것도 출력하지 않는다.

• 예제 입력

6
100 70 90 10
30 55 10 8 100
60 10 10 2 70
10 80 50 0 50
40 30 30 8 60
60 10 70 2 120
20 70 50 4 4

• 예제 출력

134
2 4 6

• 접근방식

비트마스킹으로 모든 경우의 수를 구하고 최소값을 구하면 된다.
비트가 켜져 있는지 하나씩 체크하면서 구하면 되고 해당 식은 주석에 있다.

• 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>

using namespace std;

int n, mp, mf, ms, mv;
int b, c, d, e, result = 99999999, sum;
struct A
{
    int mp, mf, ms, mv, cost;
}a[16];
map<int, vector<vector<int>>> result_v;

int main()
{
	cin >> n;
	cin >> mp >> mf >> ms >> mv;
	for (int i = 0; i < n; i++)
	{
		cin >> a[i].mp >> a[i].mf >> a[i].ms >> a[i].mv >> a[i].cost;
	}
	for (int i = 1; i < (1 << n); i++) // 비트마스킹으로 모든 경우의 수 구하기
	{
		b = c = d = e = sum = 0;
		vector<int> v;
		for (int j = 0; j < n; j++)
		{
			if (i & (1 << j)) // j번째 비트가 켜져있는지 확인하기
			{
				v.push_back(j + 1);
				b += a[j].mp;
				c += a[j].mf;
				d += a[j].ms;
				e += a[j].mv;
				sum += a[j].cost;
			}
		}
		if (b >= mp && c >= mf && d >= ms && e >= mv)
		{
			if (result >= sum)
			{
				result = sum;
				result_v[result].push_back(v);
			}
		}
	}
	if (result == 99999999) cout << -1 << endl;
	else
	{
		sort(result_v[result].begin(), result_v[result].end());
		cout << result << endl;
		for (int a : result_v[result][0])
		{
			cout << a << " ";
		}
	}
    return 0;
}

• 문제링크 : https://www.acmicpc.net/problem/19942

• 문제

한수는 캠프를 마치고 집에 돌아가려 한다. 한수는 현재 왼쪽 아래점에 있고 집은 오른쪽 위에 있다. 그리고 한수는 집에 돌아가는 방법이 다양하다. 단, 한수는 똑똑하여 한번 지나친 곳을 다시 방문하지는 않는다.

      cdef  ...f  ..ef  ..gh  cdeh  cdej  ...f 
      bT..  .T.e  .Td.  .Tfe  bTfg  bTfi  .Tde 
      a...  abcd  abc.  abcd  a...  a.gh  abc. 
거리 :  6     6     6     8     8    10    6

위 예제는 한수가 집에 돌아갈 수 있는 모든 경우를 나타낸 것이다. T로 표시된 부분은 가지 못하는 부분이다. 문제는 R x C 맵에 못가는 부분이 주어지고 거리 K가 주어지면 한수가 집까지도 도착하는 경우 중 거리가 K인 가짓수를 구하는 것이다.

• 입력

첫 줄에 정수 R(1 ≤ R ≤ 5), C(1 ≤ C ≤ 5), K(1 ≤ K ≤ R×C)가 공백으로 구분되어 주어진다. 두 번째부터 R+1번째 줄까지는 R×C 맵의 정보를 나타내는 '.'과 'T'로 구성된 길이가 C인 문자열이 주어진다.

• 출력

첫 줄에 거리가 K인 가짓수를 출력한다.

• 예제 입력

3 4 6
....
.T..
....

• 예제 출력

4

• 접근방식

방문한 곳은 다시 방문하지 않으면 visited 필요, 경우의 수를 구하는 문제여서 재귀하면서 원복 필요

• 코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int dy[4] = { -1, 0 , 1,0 };
const int dx[4] = { 0 , 1 , 0 ,-1 };
int r, c, k, visited[14][14];
char _map[14][14];
string s;

int funtion(int y, int x)
{
    if (y == 0 && x == c - 1)
    {
        if (k == visited[y][x])   return 1;
        return 0;
    }
    int result = 0;
    for (int i = 0; i < 4; i++)
    {
        int ny = y + dy[i];
        int nx = x + dx[i];
        if (ny < 0 || nx < 0 || ny >= r || nx >= c || visited[ny][nx] || _map[ny][nx] == 'T')   continue;
        visited[ny][nx] = visited[y][x] + 1;
        result += funtion(ny, nx);
        visited[ny][nx] = 0;
    }
    return result;
}

int main()
{
    cin >> r >> c >> k;
    for (int i = 0; i < r; i++)
    {
        cin >> s;
        for (int j = 0; j < c; j++)
        {
            _map[i][j] = s[j];
        }
    }
    visited[r - 1][0] = 1;
    cout << funtion(r - 1, 0);
    return 0;
}

• 문제링크 : https://www.acmicpc.net/problem/1189

• 문제

2017년 4월 5일 식목일을 맞이한 진아는 나무를 심는 대신 하이테크관 앞 화단에 꽃을 심어 등교할 때 마다 꽃길을 걷고 싶었다.

진아가 가진 꽃의 씨앗은 꽃을 심고나면 정확히 1년후에 꽃이 피므로 진아는 다음해 식목일 부터 꽃길을 걸을 수 있다.

하지만 진아에게는 꽃의 씨앗이 세개밖에 없었으므로 세 개의 꽃이 하나도 죽지 않고 1년후에 꽃잎이 만개하길 원한다.

꽃밭은 N*N의 격자 모양이고 진아는 씨앗을 (1,1)~(N,N)의 지점 중 한곳에 심을 수 있다. 꽃의 씨앗은 그림 (a)처럼 심어지며 1년 후 꽃이 피면 그림 (b)모양이 된다.

꽃을 심을 때는 주의할 점이있다. 어떤 씨앗이 꽃이 핀 뒤 다른 꽃잎(혹은 꽃술)과 닿게 될 경우 두 꽃 모두 죽어버린다. 또 화단 밖으로 꽃잎이 나가게 된다면 그 꽃은 죽어버리고 만다.

그림(c)는 세 꽃이 정상적으로 핀 모양이고 그림(d)는 두 꽃이 죽어버린 모양이다.

하이테크 앞 화단의 대여 가격은 격자의 한 점마다 다르기 때문에 진아는 서로 다른 세 씨앗을 모두 꽃이 피게하면서 가장 싼 가격에 화단을 대여하고 싶다.

단 화단을 대여할 때는 꽃잎이 핀 모양을 기준으로 대여를 해야하므로 꽃 하나당 5평의 땅을 대여해야만 한다.

돈이 많지 않은 진아를 위하여 진아가 꽃을 심기 위해 필요한 최소비용을 구해주자!

• 입력

입력의 첫째 줄에 화단의 한 변의 길이 N(6≤N≤10)이 들어온다.

이후 N개의 줄에 N개씩 화단의 지점당 가격(0≤G≤200)이 주어진다.

• 출력

꽃을 심기 위한 최소 비용을 출력한다.

• 예제 입력

6
1 0 2 3 3 4
1 1 1 1 1 1
0 0 1 1 1 1
3 9 9 0 1 99
9 11 3 1 0 3
12 3 0 0 0 1

• 예제 출력

12

• 접근방식

3개만 심으면 돼서 완전 탐색으로 접근했다. 꽃을 심으면 방문한 위치와 상 하 좌 우로 총 5개를 방문처리 하면된다.

• 코드

#include <iostream>
#include <algorithm>

using namespace std;

const int dy[4] = { -1, 0 , 1,0 };
const int dx[4] = { 0 , 1 , 0 ,-1 };
int n, visited[24][24], p[24][24], result = 999999;

int setflower(int y, int x)
{
    visited[y][x] = 1;
    int sum = p[y][x];
    for (int i = 0; i < 4; i++)
    {
        int ny = y + dy[i];
        int nx = x + dx[i];
        visited[ny][nx] = 1;
        sum += p[ny][nx];
    }
    return sum;
}

void eraseflower(int y, int x)
{
    visited[y][x] = 0;
    for (int i = 0; i < 4; i++)
    {
        int ny = y + dy[i];
        int nx = x + dx[i];
        visited[ny][nx] = 0;
    }
}

bool check(int y, int x)
{
    if (visited[y][x])   return false;
    for (int i = 0; i < 4; i++)
    {
        int ny = y + dy[i];
        int nx = x + dx[i];
        if (ny < 0 || ny >= n || nx < 0 || nx >= n || visited[ny][nx])
        {
            return false;
        }
    }
    return true;
}


void flower(int cnt, int hap)
{
    if (cnt == 3)
    {
        result = min(result, hap);
        return;
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (check(i, j))
            {
                flower(cnt + 1, hap + setflower(i, j));
                eraseflower(i, j);
            }
        }
    }
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> p[i][j];
        }
    }
    flower(0, 0);
    cout << result;
    return 0;
}

• 문제링크 : https://www.acmicpc.net/problem/14620

• 문제

사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선이 같은 위치를 갖는다. 아래 그림은 N = 5, H = 6 인 경우의 그림이고, 가로선은 없다.

초록선은 세로선을 나타내고, 초록선과 점선이 교차하는 점은 가로선을 놓을 수 있는 점이다. 가로선은 인접한 두 세로선을 연결해야 한다. 단, 두 가로선이 연속하거나 서로 접하면 안 된다. 또, 가로선은 점선 위에 있어야 한다.

위의 그림에는 가로선이 총 5개 있다. 가로선은 위의 그림과 같이 인접한 두 세로선을 연결해야 하고, 가로선을 놓을 수 있는 위치를 연결해야 한다.

사다리 게임은 각각의 세로선마다 게임을 진행하고, 세로선의 가장 위에서부터 아래 방향으로 내려가야 한다. 이때, 가로선을 만나면 가로선을 이용해 옆 세로선으로 이동한 다음, 이동한 세로선에서 아래 방향으로 이동해야 한다.

위의 그림에서 1번은 3번으로, 2번은 2번으로, 3번은 5번으로, 4번은 1번으로, 5번은 4번으로 도착하게 된다. 아래 두 그림은 1번과 2번이 어떻게 이동했는지 나타내는 그림이다.

1번 세로선	2번 세로선

사다리에 가로선을 추가해서, 사다리 게임의 결과를 조작하려고 한다. 이때, i번 세로선의 결과가 i번이 나와야 한다. 그렇게 하기 위해서 추가해야 하는 가로선 개수의 최솟값을 구하는 프로그램을 작성하시오.

• 입력

첫째 줄에 세로선의 개수 N, 가로선의 개수 M, 세로선마다 가로선을 놓을 수 있는 위치의 개수 H가 주어진다. (2 ≤ N ≤ 10, 1 ≤ H ≤ 30, 0 ≤ M ≤ (N-1)×H)

둘째 줄부터 M개의 줄에는 가로선의 정보가 한 줄에 하나씩 주어진다.

가로선의 정보는 두 정수 a과 b로 나타낸다. (1 ≤ a ≤ H, 1 ≤ b ≤ N-1) b번 세로선과 b+1번 세로선을 a번 점선 위치에서 연결했다는 의미이다.

가장 위에 있는 점선의 번호는 1번이고, 아래로 내려갈 때마다 1이 증가한다. 세로선은 가장 왼쪽에 있는 것의 번호가 1번이고, 오른쪽으로 갈 때마다 1이 증가한다.

입력으로 주어지는 가로선이 서로 연속하는 경우는 없다.

• 출력

i번 세로선의 결과가 i번이 나오도록 사다리 게임을 조작하려면, 추가해야 하는 가로선 개수의 최솟값을 출력한다. 만약, 정답이 3보다 큰 값이면 -1을 출력한다. 또, 불가능한 경우에도 -1을 출력한다.

• 예제 입력

2 0 3

2 1 3
1 1

5 5 6
1 1
3 2
2 3
5 1
5 4

6 5 6
1 1
3 2
1 3
2 5
5 5

5 8 6
1 1
2 2
3 3
4 4
3 1
4 2
5 3
6 4

5 12 6
1 1
1 3
2 2
2 4
3 1
3 3
4 2
4 4
5 1
5 3
6 2
6 4

5 6 6
1 1
3 1
5 2
4 3
2 3
1 4

• 예제 출력

0

1

3

3

-1

-1

2

• 접근방식

범위가 2<=N<=10, 1<=H<=30 이고 추가 되는 가로선의 개수가 3개가 넘으면 안되기 때문에 300C3이 최대값이다.

상태값을 저장하는 visited 필요, i번째 세로선의 결과가 i번인지 체크하는 함수 필요

• 코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int n, m, h, a, b, visited[34][34], result = 9999999;

bool itoi_check()
{
    for (int i = 1; i <= n; i++)
    {
        int start = i;
        for (int j = 1; j <= h; j++)
        {
            if (visited[j][start])  start++; //선을 오른쪽에 존재
            else if (visited[j][start - 1]) start--; // 선을 왼쪽에 존재
        }
        if (start != i) return false;
    }
    return true;
}

void line(int here, int cnt)
{
    if (cnt > 3 || cnt >= result)    return;
    if (itoi_check())
    {
        result = min(result, cnt);
        return;
    }

    for (int i = here; i <= h; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (visited[i][j] || visited[i][j - 1] || visited[i][j + 1])   continue; // 선을 그려야 하는 부분에 선이 존재하면 그리지 않음
            visited[i][j] = 1;
            line(i, cnt + 1);
            visited[i][j] = 0;
        }

    }
}

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

    for (int i = 0; i < m; i++)
    {
        cin >> a >> b;
        visited[a][b] = 1;
    }

    line(1, 0);
    cout << ((result == 9999999) ? -1 : result);

    return 0;
}

• 문제링크 : https://www.acmicpc.net/problem/15684