이것 저것 &

문제링크:https://www.acmicpc.net/problem/8980

그리디 알고리즘 문제였습니다.

우선 첫번째로 조심하셔야 하는 점은 1.도착지 2.출발지 순으로 오름차순 정렬을 해줘야 한다는 것 입니다.

저는 항상 최선의 선택을 한다는 점에 너무 집중을 해서 1.출발지 2.도착지순으로 정렬을 해서 오답을 받았습니다. ㅠㅠ

이때 

4 40

3

1 4 40

2 3 40

3 4 40

과같은 입력이 들어오면 오답처리가 됩니다. (정상출력:80 오답:40)

1) 따라서 1.도착지 2.출발지 순으로 오름차순 정렬을 해야합니다.

2) 정렬 후 m번 반복하며 해당박스들을 받을 수 있는지, 얼마나 들어갈 수 있는지 확인합니다.

( 그러기 위해서는 해당위치에 박스를 얼마나 적재했는지 표시하는 int형 배열이 필요합니다.) -> capacity

3) 1. 시작도시부터 도착도시까지 가장 많이 적재된 박스양을 구합니다.

   2. 구한 값을 통해 해당도시에서 받을 수 있는 박스량 만큼 결과 값에 더해줍니다.

   3. 시작도시부터 도착도시까지 적재한 박스양을 capacity에 더해줍니다.

3)번과 같은 과정을 m번 반복하며 결과값을 결정하는 것입니다.

정답코드입니다. 꼭 직접 작성해보세요.

#include <iostream>
#include <algorithm>
using namespace std;

struct info {
	int sender;
	int reciever;
	int cnt;

	
};

info arr[10000];
int capacity[10001] = { 0 };
int n = 0, c = 0, m = 0;
int result = 0;

bool cmp(info a, info b) {
	if (a.reciever < b.reciever)return true;
	else if (a.reciever == b.reciever)
		if (a.sender < b.sender)
			return true;
		
	return false;
}

int main() {
	
	cin >> n >> c;
	cin >> m;

	for (int i = 0; i < m; i++)
		cin >> arr[i].sender >> arr[i].reciever >> arr[i].cnt;

	sort(arr, arr + m,cmp); //오름차순 정렬 1.도착지 2.출발지 

	for (int i = 0; i < m; i++) { 
		
		int maxcnt = 0;
		for (int j = arr[i].sender; j < arr[i].reciever; j++)  //보내는곳부터 받는곳까지
			maxcnt = max(capacity[j], maxcnt); //capacity의 최대값을 저장합니다. 박스를 얼마나 넣을 수 있는 확인하기 위해

		int val = min(arr[i].cnt, c - maxcnt);
		result += val;
		
		for (int j = arr[i].sender; j < arr[i].reciever; j++) {
			capacity[j] += val; // 이동되면서 해당 공간만큼 할당해주어야 박스가 못 실리겠죠
		}

	}

	
	cout << result << endl;

}

문제 링크: https://www.acmicpc.net/problem/1969

문제만 이해하면 그리디적인 개념으로 쉽게 풀 수 있는 문제였습니다.

모든 문자열에서 인덱스값들중 가장 큰 값만을 결과문자열로 저장하고 그값과 달랐던 값을 카운트해서 결과값을 도출하면 됩니다. 

문제 조건에서 사전순으로 가장 앞서는 것을 출력한다. 라는 규칙을 주의해서 풀어 주시면 됩니다. 

아스킷 코드값을 참조하며 arr[word[j][i] - 'A']++; 의 의미가 무엇인지, 그리고 arr[26]인지 생각해보세요.

#include <iostream>
#include <string>
using namespace std;

int n, m;
string word[1000];
int result_sum = 0;
string result;
int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		cin >> word[i];
	


	for (int i = 0; i < m; i++) {
		int arr[26] = { 0 }, maxed = 0, max_index = 0;
		for (int j = 0; j < n; j++) {
			arr[word[j][i] - 'A']++; 
		}
		for (int j = 0; j < 26; j++) {
			if (maxed < arr[j]) maxed = arr[j],max_index = j;
		}
		result_sum += n - maxed;
		result += max_index + 'A';
	}

	cout << result << endl;
	cout << result_sum << endl;

}

화이팅:)

문제 링크: https://www.acmicpc.net/problem/2437

문제풀이 자체는 정말 쉬운데, 생각하는 과정이 필요했던 문제입니다.

N은 1 이상 1,000 이하이다. 라는 문제 조건을 가진다.

즉 모든 추들을 더하고 빼며 모든경우의 수를 도출(dfs방식)하는 방식으로는 시간 초과를 받을 수밖에 없다.

우선은 누적합 개념에 대해서 이해하셔야 합니다. 

for (int i = 0; i <= n; i++) {
		if (arr[i] > sum + 1) {
			break;
		}
		sum += arr[i];

	}

정렬되어 있는 상태라면 위와 같은 방법으로 O(n) 만에 측정할 수 없는 결과값을 도출할 수 있습니다.

sum은 0부터 시작되며 정렬되어 있는 arr배열에서 가장 작은 값부터 하나씩 증가하며 값을 확인합니다. sum + 1 보다 클 경우 sum + 1에 해당하는 값은 측정할 수 없기 때문에 break를 써서 반복문에서 나가게 되는 구조입니다. 

아래는 정답코드 입니다. 

#include <iostream>
#include <algorithm>
using namespace std;

int n = 0, len = 1;
int arr[1001];
int sum = 0;


int main() {
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> arr[i];

	sort(arr, arr + n); //오름차순 정렬

	for (int i = 0; i <= n; i++) {
		if (arr[i] > sum + 1) {
			break;
		}
		sum += arr[i];

	}

	cout << sum + 1 << endl;
}

위처럼 간단한 방식으로 정답을 도출할 수 있습니다.