그리디 알고리즘

문제

2875 대회 or 인턴

10610 30

어떤 수 N이 주어졌을 때, 숫자를 섞어 30의 배수를 만드는 문제
30을 소인수 분해하면 2x3x5=30이다. 이때 2의 배수는 2,4,6... 3의 배수는 모든 자리 다 더한 값이 3의 배수, 5는 끝자리가 5와 0인데 2의 배수 때문에 끝자리는 0으로 고정된다.

그리디 알고리즘
1. 우선 처음받은 숫자를 내림차순 정렬한다.
2. 모든 자리를 다 더한 값이 3의 배수인지 확인
3. 마지막 숫자가 0인지 확인

#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <functional>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#define ll long long
#define len 1001
using namespace std;

int ans, i,n;
int main(void) {
	freopen("input.txt", "r", stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	string s;
	cin >> s;
	int sum = 0;
	for (int i = 0; i < s.length(); ++i) {
		sum += s[i] - '0';
	}
	sort(s.begin(), s.end());
	if (s[0] == '0' && sum % 3 == 0) {
		reverse(s.begin(), s.end());
		cout << s << '\n';
	}
	else {
		cout << -1 << '\n';
	}
}

1783 병든 나이트

일단 조건이 매우 크다 2억이라니...

경우는 모두 4가지이고 이동 횟수가 4번 초과면 방법을 모두 1번씩은 이용해야 한다. 이때 방문할 수 있는 칸의 최대 갯수를 구하는 문제이다.

그리디 알고리즘

• 높이가 1이면 이동을 할 수 없다. 그래서 방법 1
• 높이가 2인 경우를 생각해 보자 (+2,+1)과 (+1,+2)만 이용할 수 있기에 4의 제한에 걸려 min(4,(width+1)/2) 칸을 갈 수 있다.
• 높이가 3인 경우를 생각해 보자
  
  이때는 너비가 7이하인 경우에만 다음의 경우를 사용할 수 있다. 그래서 3이상부터는 너비가 7이상인지 혹은 이하인지를 계산해야 한다.
  
  반대로 7 초과라면 4의 제한을 지키지 않아도 되기 때문에 width-2 의 땅을 밟을 수 있다.

#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <functional>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#define ll long long
#define len 1001
using namespace std;

int ans, i,n;
int main(void) {
	freopen("input.txt", "r", stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	ll height, width;
	cin >> height >> width;
	ll ans = 0;
	
	if (height == 1) {
		ans = 1;

	}
	else if (height == 2) {
		ans = min((ll)4, (width+1)/2);
	}
	else {
		if (width >= 7) {
			ans = width - 2;
		}
		else {
			ans = min((ll)4,width);
		}
	}
	cout << ans << '\n';

}

12970 AB

우선 B를 위치하고 A를 놓는 위치에 따라서 우리가 구하고자 하는 AB 쌍의 갯수가 달라지는 것을 확인할 수 있다.

B가 일렬로 세워져 있을때 A가 중간에 계속 들어가면 0 ~ a x b가 되는 문자열을 항상 만들 수 있다.

#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <functional>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#define ll long long
#define len 1001
using namespace std;

int ans, i,j,n;
int main(void) {
	freopen("input.txt", "r", stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int n, k;
	cin >> n >> k;
	for (int a = 0; a < n; ++a) {
		int b = n - a;
		if (b * a < k) continue;
		vector<int> cnt(b + 1,0);
		for (i = 0; i < a; ++i) {
			int x = min(b, k);
			cnt[x] += 1;
			k -= x;
		}
		for (i = b; i >= 0; --i) {
			for (j = 0; j < cnt[i]; ++j) {
				cout << 'A';
			}
			if (i > 0) {
				cout << 'B';
			}
		}
		return 0;
	}
	cout << -1;
	return 0;
}

12904 A와 B

A연산 : 문자열의 뒤에 A를 추가
B연산 : 문자열을 뒤집고 뒤에 B를 추가

이 문제는 조금 다르게 생각해서 풀어보자 A는 문자열의 뒤에 A를 추가하고
B는 뒤집어서 B를 뒤에 추가한다.

그렇다면 S문자와 T 문자를 비교해 S를 T로 만든다고 하면
T에서 S로 하는게 더 빠르지 않을까?

이렇게 하나씩 줄이는게 최적해를 충족할 수 있을까?
가능하다.

#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <cstring>
#include <cstdio>
#include <functional>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <ctime>
#include <cmath>
#include <stack>
#include <string>
#include <queue>
#define ll long long
#define len 1001
using namespace std;

int ans, i,n;
int main(void) {
	freopen("input.txt", "r", stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	string s, t;
	cin >> s;
	cin >> t;

	while (s.length() != t.length()) {
		if (t[t.length()-1] == 'A') {
			t.pop_back();
		}
		else {
			t.pop_back();
			reverse(t.begin(), t.end());
		}
	}
	if (s != t) {
		cout << 0 << '\n';
	}
	else {
		cout << 1 << '\n';
	}
}

1201 NMK

2873 롤러코스터

12919 A와 B2