굳건하게

문제 : https://www.acmicpc.net/problem/15650

[알고리즘풀이]

중복을 체크해줘야 되므로 visited 배열을 활용하고, 오름차순으로 진행해야 되므로, 가장 마지막에 담긴 값을 이용해서 백트레킹을 설계한다.

#include<iostream>
#include<vector>

using namespace std;

bool visited[9];

int m, n;

void bt(int, int);

int main(void) {
	cin >> n >> m;
	for (int i = 1; i <= n - m + 1; i++) {
		visited[i] = true;
		bt(1,i);
		visited[i] = false;
	}
}

void bt(int count, int start) {
	if (count == m) {
		for (int k = 1; k <= n; k++)
			if (visited[k])
				cout << k << ' ';
		cout << '\n';
		return;
	}
	for (int k = start; k <= n; k++) {
		if(visited[k] == false){
			visited[k] = true;
			bt(count + 1, k);
			visited[k] = false;
		}
	}

}

문제 : https://www.acmicpc.net/problem/15649

[알고리즘풀이]

중복을 허락하지 않으면서 모든 경우를 뽑아야 하므로, 방문한 지점을 체크하는 배열을 활용한 백트레킹 기법으로 문제를 해결한다.

#include<iostream>
#include<vector>
using namespace std;

int n, m;
bool visited[9];
vector<int> v;
void bt(int);

int main(void) {
	cin >> n >> m;
	bt(0);
}

void bt(int cnt) {
	if (cnt == m) {
		for (int i = 0; i < m; i++)
			cout << v[i] << ' ';
		cout << '\n';
		return;
	}
	for (int i = 1; i <= n; i++) {
		if(!visited[i]){
			visited[i] = true;
			v.push_back(i);
			bt(cnt + 1);
			visited[i] = false;
			v.pop_back();
		}
	}
}

문제 : https://www.acmicpc.net/problem/8896

[알고리즘풀이]

단순 구현 문제입니다.

각 라운드마다 가위, 바위, 보를 카운팅 한 후 각 경우마다 패배자를 Check해서 1명이 남을 때까지 라운드를 진행합니다.

#include<iostream>
#include<string>

using namespace std;

string list[11];

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

	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		bool check[11] = {}; // i번째 선수가 졌으면 check[i] = true;
		bool flag = false;
		for (int i = 1; i <= n; i++)
			cin >> list[i];
		for (int i = 0; i < list[1].length(); i++) {
			bool RPS[3] = {}; // R P S 나온걸체크
			for (int j = 1; j <= n; j++) {
				if (check[j] == true) // 이미 기존에 진사람
					continue;
				if (list[j][i] == 'R')
					RPS[0] = true;
				if (list[j][i] == 'P')
					RPS[1] = true;
				if (list[j][i] == 'S')
					RPS[2] = true;
			}
			// R P S 가 다 나온 경우.
			if (RPS[0] && RPS[1] && RPS[2])
				continue;
			// R P 가 나온 경우
			if (RPS[0] && RPS[1] && !RPS[2]) {
				for (int j = 1; j <= n; j++)
					if (check[j] == false && list[j][i] == 'R')
						check[j] = true;
			}
			// R S 가 나온 경우
			if (RPS[0] && !RPS[1] && RPS[2]) {
				for (int j = 1; j <= n; j++)
					if (check[j] ==false && list[j][i] == 'S')
						check[j] = true;
			}
			// P S 가 나온 경우
			if (!RPS[0] && RPS[1] && RPS[2]) {
				for (int j = 1; j <= n; j++)
					if (check[j] == false && list[j][i] == 'P')
						check[j] = true;
			}
			int count = 0, index = 0;
			for (int j = 1; j <= n; j++) {
				if (check[j] == false) {
					count++;
					index = j;
				}
			}
			if (count == 1){
				cout << index << '\n';
				flag = true;

				break;
			}
		}
		if (!flag)
			cout << 0 << '\n';
	}
}

문제 : https://www.acmicpc.net/problem/2240

[알고리즘풀이]

t[x] : x 초에 떨어지는 자두의 위치. ( 1이면 1번 나무, 2이면 2번 나무 )

dp[x][y][z] : x 초까지 y 번 방향을 전환했고 현재 z 위치에서 최댓값.

( z 가 0일 때 1번 나무, 1일 때 2번 나무라고 정의 )

-초기값

dp[x][0][0] : x 초에 0번 방향을 전환했고 1번 나무 위치에서 최댓값.

               = 1번 나무에서 지금까지 떨어진 자두의 수 ( 방향 전환 없으므로 1번 나무에서 계속 있었다. )

dp[x][1][1] : x 초에 1번 방향을 전환했고 2번 나무 위치에서 최댓값.

               = ( x - 1 초에서 0번 방향을 전환했고, 1번 나무 위치에서 최댓값 , x - 1 초에서 1번 방향을 전환했고,

                   2번 나 무 위치에서 최대값 ) 중 더 큰 값에 t[x] 가 2라면 + 1을 해준다.

-점화식

dp[x][y][0] = max(dp[x-1][y-1][1], dp[x-1][y][0]) 에 t[x] 가 1이라면 1을 더해준다.

dp[x][y][1] = max(dp[x-1][y-1][0], dp[x-1][y][1]) 에 t[x] 가 2라면 1을 더해준다.

#include<iostream>
#include<algorithm>

using namespace std;

int t[1001];
int n, m;
int dp[1001][31][2];

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	// 입력
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> t[i];
	}
	// 초기값
	for (int i = 1; i <= n; i++) {
		dp[i][0][0] = dp[i - 1][0][0];
		dp[i][1][1] = max(dp[i - 1][1][1], dp[i - 1][0][0]);
		if (t[i] == 1)
			dp[i][0][0]++;
		if (t[i] == 2)
			dp[i][1][1]++;
	}
	// 점화식
	for (int i = 2; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			dp[i][j][0] = max(dp[i - 1][j - 1][1], dp[i - 1][j][0]);
			dp[i][j][1] = max(dp[i - 1][j - 1][0], dp[i - 1][j][1]);
			if (t[i] == 1)
				dp[i][j][0]++;
			else
				dp[i][j][1]++;
		}
	}
	int result = 0;
	for (int j = 0; j <= m; j++)
		for (int k = 0; k < 2; k++)
			if (dp[n][j][k] > result)
				result = dp[n][j][k];
	cout << result;
}