급하게임개발

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

이 문제는 풀다가 이상하다 왤케 답이 완전 다르게 나오지 하다가 보니까 내가 문제를 잘못이해하고 있었다

2
5
3 2
1 4
4 1
2 3
5 5
7
3 6
7 3
4 2
1 4
5 7
2 5
6 1

여기 나오는 이값들은 사실 순위였던 것이었다. 그래서 문제를 이상하게 풀고 있었다. 이문제는 간단히 설명하자면

하나의 성적을 기준으로 줄을 세워놓은 다음에 다음애들을 비교하여 그 줄에서 나의 다음(나보다 성적이 낮은) 애들의 다른 성적을 비교하여 나보다 성적이 낮으면 그친구를 쳐내는 방식이다 예를 들면 서류심사 성적으로 줄을 세워놓은 다음에

나보다 서려심사를 못봤는데 나보다 면접 성적 까지 낮으면 그 사람은 세지 않는 방법이다

자 위 그림을 보자 서류 성적 순대로 정렬 한다 이렇게 정렬하면 내 다음에 나오는 애는 무조건 나보다 서류 성적은 낮은 상태가 된다. 그러므로 나보다 서류성적이 낮은애랑 나의 면접성적을 비교한다 나의 다음애가 나보다 면접 성적이 높으니 count를 하고 지금까지 비교했을 때 가장 높은 성적을 maxnum에 저장해주고 countnum을 하나 증가시켜준다 즉 현재 서류성적순으로 정렬했을때 가장 높은 면접성적은 3등이다 이제 그다음에 나오는 애는 3등보다 면접 성적이 높으면 maxnum에 갱신해주고 쳐내지 않지만  다음애가 이전까지 비교해서 나온성적인 3등보다 낮으면 쳐낸다 계속 이렇게 반복하여 countnum의 값을 답으로 출력해주면 된다

#include <iostream>
#include <algorithm>
using namespace std;
pair<int, int> score[100000];
int answer[20];
int main() {
	int testnum;
	cin >> testnum;
	for (int i = 0; i < testnum; i++) {
		int countnum = 0;
		int candidatenum;
		cin >> candidatenum;
		for (int j = 0; j < candidatenum; j++) {
			cin >> score[j].first >> score[j].second;
		}
		sort(score, score + candidatenum);
		int maxscore = score[0].second;

		for (int j = 0; j < candidatenum; j++) {
			if (score[j].second <= maxscore) {
				countnum++;
				maxscore = score[j].second;
			}

		}
		answer[i] = countnum;
	}
	for (int i = 0; i < testnum; i++) {
		cout << answer[i] << '\n';
	}
}

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

얘는 살짝 만 생각하면 답이나오는 문제 였다. 문제 푸는 방법이 퍼뜩퍼뜩 났으면 좋겠는데 아직 수련이 부족해서 시간이 오래 걸린다.

이 문제는 간단하다 내이전에 나온 최댓값과 나를 더한값과 나 혼자 값중에 더큰애를 선택해주면 되는 문제였다.

그 이유는 어찌됬든 더하는 수가 양수라면 값은 증가하기 때문이다

10
10 -4 3 1 5 6 -35 12 21 -1

즉 이런식으로 입력이 주어지면

dp[1]은 -4와 6중에 선택한다

dp[2]는 3과 9중에 선택한다

dp[3]은 10과 1중에 선택한다

이런식으로 dp값이 바뀐다 즉 점화식은

max(dp[i-1]+arr[i],arr[i])값이 된다

#include <iostream>
using namespace std;
int arr[100000];
int dp[100000];
int max(int x,int y) {
	return x > y ? x:y;
}
int main() {
	int inputnum;
	int maxnum;
	cin >> inputnum;
	for (int i = 0; i < inputnum; i++) {
		cin >> arr[i];
	}
	dp[0]=arr[0];
	maxnum = dp[0];
	for (int i = 1; i < inputnum; i++) {
		dp[i] = max(dp[i - 1] + arr[i], arr[i]);
	}

	for (int i = 0; i < inputnum; i++) {
		if (dp[i] > maxnum) {
			maxnum = dp[i];
		}
	}
	cout << maxnum;
}