Silver 2839
첫시도
greedy 알고리즘은 '당장 눈 앞에 보이는 최적의 상황만을 쫓는 알고리즘'으로 항상 최적의 결과를 도출하는 것은 아니지만 어느 정도 최적의 해에 근사한 값을 빠르게 구할 수 있다는 장점이 있습니다.
int main() {
int n, cnt=0;
cin >> n;
cnt = cnt+n / 5;
n = n % 5;
cnt = cnt + n / 3;
n = n % 3;
if (n != 0) { cout << "-1"; return 1; }
cout << cnt;
return 0;
}그리디 알고리즘은 최적의 해를 보장하는 경우도 많으나 애석하게도 최적의 해를 보장하지 못하는 경우가 더 많다 그럴 때 다이나믹 프로그래밍 등의 알고리즘 기법을 적용하여야 합니다.
EX)
입력 11 일때
5 5 1 로 cnt = 3이라는 최적의 값을 도출하지만
입력 9 일때
5 3 으로 3 3 3 해서 총 3번이란 최솟값이 나와야하지만 cnt = -1값이 나온다
두번째시도
#include <iostream>
using namespace std;
int main() {
int N,A;
cin >> N;
for (int i = 0; 3 * i <= N; i++) {
A = (N - 3*i) / 5;
if ((N - 3 * i) % 5 ==0) {
cout << A + i; return 0;
}
}
cout << -1;
return 0;
}그리디알고리즘의 개념 당장 눈 앞에 보이는 최선이라는 개념을 활용하여 3의 개수를 줄이고 5의 개수를 최대한 늘리는 방식으로 for문을 이용하여 3이 0개일때부터 3*i가 N까지 3의 개수를 1개씩 추가하면서 5의 개수를 줄이는 방식을 택했다!
Silver 1931
첫시도
#include <iostream>
#include <vector>
#include<algorithm>
using namespace std;
class Dot {
public:int x, y;
Dot(int x, int y) {
this->x=x; this->y=y;
}
};
bool compare(Dot a, Dot b) {
if (a.x == b.x) {
return a.y < b.y;
}
else {
return a.x < b.x;
}
}
int main() {
vector <Dot> v;
int x,y,N,cnt=1,max=0,mid=0;
cin >> N;
for (int i = 0; i < N; i++) {
cin >> x >> y;
v.push_back(Dot(x, y));
}
sort(v.begin(), v.end(), compare);
for (int i = 0; i < N; i++) {
cnt = 1;
mid = v[i].y;
for (int j = i + 1; j < N; j++) {
if (mid <= v[j].x) {
mid = v[j].y;
cnt++;
}
}
if (max < cnt) {
max = cnt;
}
}
cout << max;
return 0;
}문제에서 주어진 제한시간이 2초인데
N의 최댓값 : 100,000 (10만)
N^2 : 10,000,000,000 (100억)
2초(=2억) < 100억(=10초)이므로
- 시간 초과!
for문 두개 돌리기 전에 계산을 해보고 접근방식을 다르게 했어야했다!
두번째시도
#include <iostream>
#include <vector>
#include<algorithm>
using namespace std;
class Dot {
public:int x, y;
Dot(int x, int y) {
this->x=x; this->y=y;
}
};
bool compare(Dot a, Dot b) {
if (a.y == b.y) {
return a.x < b.x;
}
else {
return a.y < b.y;
}
}
int main() {
vector <Dot> v;
int x,y,N,cnt=1,from=0;
cin >> N;
for (int i = 0; i < N; i++) {
cin >> x >> y;
v.push_back(Dot(x, y));
}
sort(v.begin(), v.end(), compare);
from = v[0].y;
for (int i = 1; i < N; i++) {
if (from<=v[i].x) {
cnt++;
from = v[i].y;
}
}
cout << cnt;
return 0;
}- 그리디 알고리즘을 이용하였습니다.
-
문제가 당장 주어진 이득만 쫓아가도 예외가 없는 상황이라 주어진 이득인 회의 시작시간과 끝나는 시간이 가장 짧은 것만 쫓아갔다
-
회의 시작시간 기준으로 오름차순을 했을때는 for문이 두개가 필요하고 for문 두개를 이용하면 위처럼 시간초과가 난다.
-
정렬을 끝나는 시간 기준으로 정렬을하고 끝나는 시간이 같을 경우에는 시작시간이 빠른 것을 기준으로 정렬을 하였다.
-
이후 시작점의
from의y를 기준으로v[i].x가 더 크면from기준으로 바꿔주고count++해주고count를 출력한다.
Silver 1946
첫시도
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
using namespace std;
int main() {
int T, Tcount = 0, x, y, cnt = 1,m=0;
cin >> T;
while (Tcount < T) {
cnt = 1;
Tcount++;
int N;
cin >> N;
pair<int, int> p1;
vector <pair<int, int>> v;
for (int i = 0; i < N; i++) {
cin >> x >> y;
p1 = make_pair(x, y);
v.push_back(p1);
}
sort(v.begin(), v.end());
m = v[0].second;
for (int i = 1; i < N; i++) {
if (m > v[i].second) {
m = v[i].second;
cnt++;
}
}
cout << cnt << '\n';
}
return 0;
}pair을 이용하여 두쌍의 서류심사 성적과 면접시험 성적을 한번에 저장하고 서류심사 성적이 높은 순서대로 정렬을 했다.
- 서류 면접
- A : 1 3
- B : 2 5
- C : 3 6
- D : 4 2
- E : 5 7
- F : 6 1
- G : 7 3
위처럼 정렬이 된다.
문제에서 서류심사 성적과 면접시험 성적이 다른 지원자보다 모두 떨어진다면 선발 되지 않는다(=둘 중 하나라도 다른 지원자보다 높으면 채용된다)
라는 개념을 가지고 풀었다.
A는 서류가 1등이니 무조건 뽑히고
그 밑으로는 뽑히려면 A의 면접 점수(m)보다 높아야 한다.
m보다 높은 값은 계속 초기화해 가면서 cnt++를 해주면 그리디알고리즘으로 문제를 해결할 수 있다.
Silver 13305
첫시도
#include <iostream>
using namespace std;
int main() {
int N,min=1000000000,car=0,index=0;
cin >> N;
int km[99999]={0};
int L[100000]={0};
for (int i = 0; i < N - 1; i++) {
cin >> km[i];
}
for (int i = 0; i < N; i++) {
cin >> L[i];
}
for (int i = 0; i < N - 1; i++) {
if (min > L[i]) {
min = L[i];
index = i;
}
}
for (int i = 0; i <= index - 1; i++) {
car = car + L[i] * km[i];
}
for (int i = index; i < N - 1; i++) {
car = car + min * km[i];
}
cout << car;
return 0;
}부분성공 17점!
Silver 1049
#include <iostream>
using namespace std;
int N, M;
int set = 1000;
int EA = 1000;
int ans;
int main() {
cin >> N>> M;
for (int i = 0; i < M; i++) {
int x, y;
cin >> x >> y;
if (x < set) { set = x; }
if (y < EA) { EA = y; }
}
if (EA == 0 || set == 0) { cout << 0; return 0; }
if (set >= 6 * EA) {
ans = EA * N;
}
else {
ans = (N / 6) * set;
if (N % 6 > set / EA) {
ans = ans + set;
}
else {
ans = ans + (N % 6) * EA;
}
}
cout << ans << '\n';
return 0;
}내 생각대로 6개 세트로 구입하는게 낱개 6개 따로 구입하는 것보다 무조건 싸다라는 고정관념을 가지고 풀었다가 틀렸다.
- 예제
6 1
13 2를 입력해보면 전에 풀었던 코드에서는 13이 나오지만 세트로 6개 사는 것이 아닌 낱개로 6개를 사면 12라는 더 싼 값으로 구입할 수 있다.
그래서 세트가 더 싼경우와 아닌 경우 두개로 분리하니 정답!
-> 내가 혼자 테스트케이스를 생각해보고 대입하면서 푸는 연습을 해야한다!
이를 위해선 문제를 정확하게 이해하는게 중요하다 문제만 정확하게 이해하고 예외처리도 생각해놓으면 코드도 짧아지고 실수도 없어질 뿐더러 짧은 시간안에 풀 수 있다.
Gold 1461
첫 시도
#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
using namespace std;
int N, M,sum;
vector<int> p;
vector<int> m;
void f(vector<int>&b, vector<int>&s) {
int index=s.size() % M - 1;
if (s.size()%M == 0) { index = M-1; }
for (int i = index; i < s.size(); i=i+M) {
sum = sum + 2*abs(s[i]);
}
int index1 = b.size() % M - 1;
if (b.size()%M == 0) { index1 = M - 1; }
for (int i = index1; i < b.size(); i = i + M) {
sum = sum + 2 * abs(b[i]);
}
sum = sum - abs(b.back());
}
int main() {
cin >> N >> M;
for (int i = 0; i < N; i++) {
int x;
cin >> x;
if (x > 0) {
p.push_back(x);
}
else {
m.push_back(x);
}
}
sort(p.begin(), p.end());
sort(m.begin(), m.end(), greater<int>());
if (p.empty() || m.empty()) {
if (!p.empty()) {
f(p, m);
}
else {
if (!m.empty()) {
f(m, p);
}
}
}
else {
if (p.back() > -m.back()) {
f(p, m);
}
else {
f(m, p);
}
}
cout << sum << '\n';
return 0;
}첫번째 풀이는 답은 나오긴 했는데 코드가 워낙 복잡해 나조차도 이해하기 힘든 코드이다.
음수 벡터와 양수 벡터를 나누어서 숫자의 개수를 M으로 나누어 나눈 값부터 i=i+M을 해주어 2 X 원소를 해주었지만 너무 복잡하다 또 모두 양수일 때와 모두 음수일 때
back을 호출하는 과정에서 오류가 생겨서 음수 벡터와 양수 벡터가 empty()일때와 아닐 때로 나누어 더 복잡해졌다.
그래서 더 간단한 코드를 짜보았습니다.
#include <iostream>
#include <algorithm>
using namespace std;
int arr[10001];
int index;
int ans;
int main() {
int N, M;
cin >> N >> M;
for (int i = 0; i < N; i++) {
cin >> arr[i];
if (arr[i] < 0) {
index++;
}
}
sort(arr, arr + N);
for (int i = N - 1; i >= index; i = i - M) {
ans = ans + arr[i] * 2;
}
for (int i = 0; i < index; i = i + M) {
ans = ans + abs(arr[i]) * 2;
}
ans = ans - max(abs(arr[0]), abs(arr[N - 1]));
cout << ans << '\n';
return 0;
}0을 기준으로 보는 것이 아닌 전체를 기준으로 보면 결국은 arr원소에 +든 -든 원소를 모두 넣고 정렬 후 0을 기준으로 양쪽 끝에서 부터 M칸 씩 넘으면서 2 X 원소를 해준 후 마지막에 +, -의 절댓값중 더 큰 것을 빼주면 간단하게 풀리는 문제였다.
->깨달은 점
1. 벡터나 stack pop같은 경우 push를 하지 않고 top호출이나 back호출 등을 주의해야한다.
2. 관점을 바꾸는 연습을 해야 함 구현이 어려우면 다양한 시각에서 볼 줄 알아야한다!
3. 생각하는 연습! 생각하면 시간을 더 단축 시킬 수 있다
