[Algorithm] 5주차 스터디 - 그리디&구현(백준 11047, 13305, 11000, 21737)

A - 11047 동전 0

https://www.acmicpc.net/problem/11047

11047번: 동전 0

 

 

코드

#include <stdio.h>


int main(void) {
	int coins[10];
	int n, k, num, coin, count;

	count = 0;
	scanf_s("%d %d", &n, &k);

	for (int i = 0; i < n; i++) {
		scanf_s("%d", &num);
		coins[i] = num;
	}

	while (k != 0) {
		for (int j = 0; j < n; j++) {
			if (coins[j] <= k) {
				coin = coins[j];
			}
		}
		count += (k / coin);
		k = k % coin;
	}
	printf("%d", count);
}

 

문제 풀이

 갖고 있는 동전 중에서 가장 크기가 큰 동전을 최대한 많이 사용할 수록 사용하는 동전의 개수가 적어진다. 그래서 입력 받은 K의 값이 0이 될 때까지 K보다 작으면서 가장 큰 동전의 값으로 계속 나눠주었다. C로 문제를 풀었고, while 문 안에서 현재 K의 값보다 작되, 최대값인 동전의 종류를 찾아 count 값에는 사용하는 동전의 개수를 더해주고, k값에는 그 동전의 값으로 나눈 나머지를 넣어주었다.

 

 

B - 13305 주유소

https://www.acmicpc.net/problem/13305

13305번: 주유소

 

 

코드

#include <iostream>
#define MAX 11
using namespace std;

void init() {
	cin.tie(0); cout.tie(0);
	ios_base::sync_with_stdio(false);
}

int main()
{
	init();
	int N;
	int road[99999];
	int city[100000];
	long long min = 1000000001, cost = 0;
	int temp;
	cin >> N;
	for (int i = 0; i < N - 1; i++) {
		cin >> road[i];
	}
	for (int i = 0; i < N; i++) {
		cin >> city[i];
	}

	for (int i = 0; i < N - 1; i++) {
		if (city[i] < min) min = city[i];
		cost += min * road[i];
	}

	cout << cost;
}

 

문제 풀이

 결과값으로 출력할 최소 비용과 도시 하나가 가질 수 있는 리터 당 가격은 int 값의 범위를 넘어가기 때문에 long long 타입으로 정의해야 한다. 왼쪽에서 오른쪽까지 도시를 하나씩 이동하면서, 현재 도시의 기름 가격이 바로 이전 도시까지의 최소 기름 가격(min)보다 적을 때 현재 도시에서 기름을 넣도록 했다. for문 안에서 i 변수를 하나씩 증가해 다음 도시로 넘어갈 때마다 최소 기름 가격을 나타내는 min 변수와 현재 도시의 기름 가격을 비교한 다음, 현재 도시의 기름 가격(city[i])이 더 작은 경우, min 변수에 현재 도시의 기름 가격을 대입하였다.

 

 

C - 11000 강의실 배정

https://www.acmicpc.net/problem/11000

11000번: 강의실 배정

 

 

코드

#include <iostream>
#include<vector>
#include<algorithm>
#include<math.h>
#include<queue>

using namespace std;

void init() {
	cin.tie(0); cout.tie(0);
	ios_base::sync_with_stdio(false);
}

int main() {
	init();
	int N;
	cin >> N;
	priority_queue<int, vector<int>, greater<int>> pq;
	vector<pair<int, int>> v;
	for (int i = 0; i < N; i++)
	{
		int a, b;
		cin >> a >> b;
		v.push_back({ a,b });

	}
	sort(v.begin(), v.end());

	pq.push(v[0].second);

	int ans = 1;
	for (int i = 1; i < v.size(); i++)
	{
		while (!pq.empty() && pq.top() <= v[i].first)
			pq.pop();
		pq.push(v[i].second);
		ans = max(ans, (int)pq.size());
	}
	cout << ans;
}

 

문제 풀이

 먼저 벡터를 사용해 입력받은 수업의 시작 시간과 끝나는 시간을 한 쌍으로 저장한 다음, 오름차순으로 정렬해주었다. 그 다음에 우선순위 큐에서 수업이 끝나는 시간을 오름차순 정렬시키며 필요한 교실의 개수가 몇 개인지 계산했다. 만약 해당 수업 시간의 끝나는 시간이 큐의 top(가장 일찍 끝나는 수업의 시간)보다 더 늦는 경우에는 큐의 top 값을 pop한 뒤에 더 늦게 끝나는 수업 시간을 push하고, 그렇지 않은 경우에는 바로 push를 해 큐의 사이즈를 하나 증가시킨다. 이 우선순위 큐의 사이즈를 이용해 필요한 교실의 개수를 구할 수 있었다.

 

 

D - 21737 SMUPC 계산기

https://www.acmicpc.net/problem/21737

21737번: SMUPC 계산기

 

 

 

코드

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

void init() {
	cin.tie(0); cout.tie(0);
	ios_base::sync_with_stdio(false);
}

int main() {
	init();

	int N, result = 0;
	string S, temp;
	char oper = '+';
	bool isC = false;

	cin >> N >> S;
	
	for (int i = 0; i < S.length(); i++) {
		if (S[i] >= '0' && S[i] <= '9')
			temp += S[i];
		else {
			switch (oper) {
			case '+':
				result += stoi(temp);
				break;
			case '-':
				result -= stoi(temp);
				break;
			case '*':
				result *= stoi(temp);
				break;
			case '/':
				result /= stoi(temp);
				break;
			}
			temp = "0";

			if (S[i] == 'P') oper = '+';
			else if (S[i] == 'M') oper = '*';
			else if (S[i] == 'S') oper = '-';
			else if (S[i] == 'U') oper = '/';
			else {
				isC = true;
				oper = '+';
				cout << result << " ";
			}
		}
	}

	if (!isC) cout << "NO OUTPUT";
}

 

문제 풀이

 별 어려움 없이 입력받은 String 변수를 인덱스로 처음부터 끝까지 반복문을 돌며 조건문으로 계산해주면 된다. 만약 스트링 변수의 해당 문자가 숫자('0'보다 크고 '9'보다 작거나 같을 때)일 경우, 피연산자 변수인 temp로 옮겨준다. 반면에 숫자가 아니라 연산자인 경우에는 temp 값을 oper 변수에 저장된 바로 이전 연산자로 계산한다. 그 다음, 현재 인덱스의 연산자 값을 oper 변수에 다시 저장해 다음 연산에 사용할 수 있도록 하면 된다.