3. 그리디 알고리즘(2)
그리디 알고리즘
문제
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
Author And Source
이 문제에 관하여(3. 그리디 알고리즘(2)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@tonyhan18/4.-그리디-알고리즘2저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)