- 동전 0
그리디 알고리즘 이용해 문제를 해결한다 동전을 배열 coin에 넣고 목표액 k를 변수에 저장한다
반복문을통해 k !=0 동안 만약 coin[n](가장 비싼 코인) 보다 k가 같거나 크다면 k에서 동전값을 빼고 카운트를 증가시키고 만약 코인이 더크다면 n--을 작은 코인으로 다시 수행한다 가장 큰코인부터 알고리즘을 수행하기때문에 최소한의 코인을 사용할수있다.
#include <iostream>
using namespace std;
int main()
{
int n, k, cnt = 0;
int coin[10];
cin >> n >> k;
for (int i = 0; i < n; i++)
{
cin >> coin[i];
}
n--;
while (0 != k)
{
if (k - coin[n] < 0)
{
n--;
continue;
}
k -= coin[n];
cnt++;
}
cout << cnt << endl;
}2.회의실 배정
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Time
{
int begin_time;
int end_time;
};
bool cmp(Time t1, Time t2)
{
if (t1.end_time == t2.end_time)
return t1.begin_time < t2.begin_time;
else
return t1.end_time < t2.end_time;
}
int main()
{
int num, start_T = 0,cnt=0;
cin >> num;
vector < Time> v(num);
for (int i = 0; i < num; i++)
{
cin >> v[i].begin_time >> v[i].end_time;
}
sort(v.begin(), v.end(),cmp);
for (int i = 0; i < num; i++)
{
if (start_T <= v[i].begin_time)
{
start_T = v[i].end_time;
cnt++;
}
}
cout << cnt << endl;
}회의를 최대 몇개 진행하는지 알기위해서 정렬을 진행해야한다 정렬은 단순 정렬이아닌 시작시간과 종료시간이 기록된 구조체에서 만약 끝나는 시간이 같다면 시작시간이 큰쪽으로 아니라면 종료시간이 큰쪽으로 정렬을 진행한다 이렇다면 종료시간이 가장 짧고 시작시간도 짧은 순으로 정렬이된다
다음 종료시간을따라 정하기위해 start_t를 0으로 정한뒤 만약에 정렬된 처음부터 시작시간이 더크다면 그회의를 진행하므로 종료시간을 그 회의 종료시간으로 바꾸고 카운트를 1증가 시켜준다.
3.ATM
대기시간의 최소값을 구하기 위해선 오름차순으로 정렬을 해야한다 sort함수를 통해 정렬을하고
temp 값에 기존 배열을 저장하고 res에 temp와 해당 대기시간을 더하는식으로 최소값을 구한다.
#include <iostream>
#include <algorithm>
using namespace std;
int main(void)
{
int people[1000];
int n,res = 0;
int temp = 0;
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> people[i];
}
sort(people, people + n);
for (int i = 0; i < n; i++)
{
res += temp + people[i];
temp = temp + people[i];
}
cout << res << endl;
}
- 잃어버린 괄호
#include <iostream>
#include <cstring>
using namespace std;
int main(void)
{
char str[51];
int arr[25] = { 0, };
int j = 0,ans = 0;
int len;
int sum = 0, temp = 0;
cin >> str;
len = strlen(str);
for (int i = 0; i < len; i++)
{
if (str[i] == '-')
{
sum += temp;
arr[j++] = sum;
sum = 0;
temp = 0;
}
else if (str[i] == '+')
{
sum += temp;
temp = 0;
}
else
{
temp *= 10;
temp += str[i] - '0';
}
}
sum += temp;
arr[j++] = sum;
ans = arr[0];
for (int i = 1; i < j; i++)
{
ans -= arr[i];
}
cout << ans << endl;
}최소값을 얻기위해선 -부터 -까지의 값을 괄호로 묶어 빼는값을 최대로 해주어야한다
문자열을 받은뒤 앞에서부터 문자열을 탐색하며 3가지 경우로 나뉜다
숫자인경우 : 한자리 씩 temp값에 저장하며 +,-까지의 값을 temp에 저장한다
+인경우 : 이전까지의 temp 값을 sum에 저장하고 temp를 0으로 초기화한다
-인경우 : temp값을 sum에 저장하고 arr[j]에 sum값을 저장한후 sum temp를 0으로 초기화한후 넘어간다
이 방식으로 문자열을 끝까지 탐색하면 -을 만나기전까지의 더해진값이 arr[0]에 이후 각각 -을 만날때까지의 값이 arr에 저장될것이다 그러므로 최소값은 처음나온값인 arr[0]에서 나머지를 빼준값을 결정해주면된다.
5.주유소
#include <iostream>
using namespace std;
long long d[100000];
long long p[100000];
long long sum = 0;
int main(void)
{
int n;
long long greed;
cin >> n;
for (int i = 0; i < n - 1; i++)
{
cin >> d[i];
}
for (int i = 0; i < n; i++)
{
cin >> p[i];
}
greed = p[0];
for (int i = 0; i < n - 1; i++)
{
if (greed > p[i])
greed = p[i];
sum += greed * d[i];
}
cout << sum << endl;
}단순 카운트값이 아닌경우 자료형은 long long형을 사용한다 핵심 알고리즘은 배열을 내림차순으로 초기화하면된다는것이다 앞에 나올값이 더크다면 그전에 저렴한곳에서 기름을 미리 채우는 방식을 사용한다 예를 들어 price배열이 {7,5,8,7,3,2,1} 일경우 2번쨰 도시에서 7도시까지 저렴한 5가격의 기름을 채우는게 이득이므로 이배열은 { 7,5,5,5,3,2,1}이라고 볼수있다 이 배열의 각 거리를 곱해준다면 최소한의 기름값을 알수있다.
