굳건하게

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

[ 알고리즘풀이 ]

 전깃줄의 상태가 들어오면 한쪽을 기준으로 sorting 한 후, 다른 쪽에서 LIS를 구하면 정답을 얻어낼 수 있습니다.

예시)

 왼쪽 전봇대를 기준으로 Sorting을 해보겠습니다.

 그 후, 왼쪽 전봇대는 Sorting이 되었으므로, 오른쪽 전봇대에서 가장 긴 증가하는 부분 수열을 찾는다면 그 부분 수열은 왼쪽 전봇대는 이미 Sorting 되어 있고, 오른쪽 전봇대에서도 증가하고 있으므로 서로 엉키지 않습니다! 즉, 서로 최대한 교차하지 않는 상태가 됩니다. 따라서, 가장 긴 증가 부분 수열의 길이를 구하고 N에서 빼준다면 제거해야 되는 전깃줄의 최소 개수를 얻어낼 수 있습니다.

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

using namespace std;

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

	int N, a, b, dp[100] = {};
	vector<pair<int, int>> v;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> a >> b;
		v.push_back(make_pair(a, b));
	}
	sort(v.begin(), v.end());
	// LIS구하는부분
	dp[0] = 1;
	for (int i = 1; i < N; i++) {
		int m = 0;
		for (int j = 0; j < i; j++)
			if (v[j].second < v[i].second)
				m = max(m, dp[j]);
		dp[i] = m + 1;
	}
	int m = 0;
	for (int i = 0; i < N; i++)
		m = max(dp[i], m);
	cout << N - m;
}

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

[ 알고리즘풀이 ]

Lucky Set을 정렬한 후, N의 상대적인 위치를 파악해 Lucky Set에서 left, right 를 설정합니다.

left 와 N이 같다면 0을 출력하고 아니라면 경우의 수를 모두 출력해주면 됩니다.

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

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int N, list[1002] = {}, L, left, right;
	cin >> N;
	for (int i = 1; i <= N; i++)
		cin >> list[i];
	sort(list, list + N + 1);

	cin >> L;
	for (int i = 0; i <= N; i++)
		if (list[i] <= L && L < list[i + 1]) {
			left = list[i];
			right = list[i + 1];
			break;
		}
	if (L == left)
		cout << 0;
	else
		cout << (L - left) * (right - L) - 1;
	return 0;
}

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

[ 알고리즘풀이 ]

1. Backtracking 을 이용해 가능한 모든 타순에 대해서 게임을 진행합니다. ( 이때, 1번 선수는 4번 타자로 선발된 경우만 게임을 진행합니다. )

2. 게임은 N 이닝 동안 현재 주자 상태와 현재 타석에 있는 타자의 결과에 따라서 score를 계산해주면 됩니다.

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

using namespace std;

int N, result[50][9] = {}, ans = -1;

int startGame(vector<int> batting) {
	int score = 0, batter = 0, out = 0;
	for (int i = 0; i < N; i++) {
		out = 0;
		bool runner[3] = {};
		while (out < 3) {
			if (result[i][batting[batter]] == 0)
				out++;
			else {
				// 기존에 있던 주자들
				for (int j = 2; j >= 0; j--) {
					if(runner[j]){
						if (j + result[i][batting[batter]] >= 3)
							score++;
						else
							runner[j + result[i][batting[batter]]] = true;
						runner[j] = false;
					}
				}
				// 타자
				if (result[i][batting[batter]] == 4)
					score++;
				else
					runner[result[i][batting[batter]] - 1] = true;
			}

			batter = (batter + 1) % 9;
		}
	}
	return score;
}

void backTracking(vector<int> batting, bool check[9]) {
	if (batting.size() == 9) {
		if(batting[3] == 0)
			ans = max(ans, startGame(batting));
		return;
	}
	for(int i = 0; i < 9; i++)
		if (!check[i]) {
			batting.push_back(i);
			check[i] = true;
			backTracking(batting, check);
			check[i] = false;
			batting.pop_back();
		}
	return;
}

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

	cin >> N;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < 9; j++)
			cin >> result[i][j];

	vector<int> batting;
	bool check[9] = {};
	for (int i = 0; i < 9; i++) {
		batting.push_back(i);
		check[i] = true;
		backTracking(batting, check);
		check[i] = false;
		batting.pop_back();
	}
	cout << ans;
	return 0;
}

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

[ 알고리즘풀이 ]

 브랜드 중에서 패키지가 제일 싼 가격과 낱개가 제일 싼 가격을 뽑아낸 후, N 개를 모두 낱개로 사는 경우, N 개를 모두 패키지로 사는 경우, N 개를 최대한 패키지로 사고 남은 부분을 낱개로 사는 경우 중 가장 작은 값을 출력해주면 됩니다.

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

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

	int N, M, a, b, six = 987654321, one = 987654321, ans = 987654321;
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		cin >> a >> b;
		six = min(six, a);
		one = min(one, b);
	}
	ans = min(ans, one * N);
	if (N % 6 == 0)
		ans = min(ans, six * (N / 6));
	else{
		ans = min(ans, six * (N / 6) + one * (N - 6 *(N / 6)));
		ans = min(ans, six * (N / 6 + 1));
	}
	cout << ans;
	return 0;
}