[그리디] 28126 Space-A c++구현

목차

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

문제

 

 

문제 구현 방향

무식하게 해보기 -> DP -> 그리디 순서로 해보면 되는데 나는 무식하게 해보아서 잘 맞았다.

물론 코드는 매우 길다..

 

 

코드 구현

#include<iostream>
#include<algorithm>
#include<string.h>
#include<map>
using namespace std;

int N, K;
string order;
int cnt = 0;
map<char, int> m;


int check(int x, int y) {
	int Mx =1, My =1;
    //처음 0 0 일 경우 맞음
	if (x == 1 && y == 1)
		return 1;
	int xGap = x - Mx;
	int yGap = y - My;
    //xgap이 0일 경우
	if (xGap == 0) {
		if (m['U'] < yGap)
			return 0;
		else
			return 1;
	}
    //ygap이 0일 경우
	else if (yGap == 0) {
		if (m['R'] < xGap)
			return 0;
		else
			return 1;
	}
    //둘다 0이 아닐 경우
	else if (xGap !=0 && yGap !=0 ) {
		if (xGap < yGap) {
			if (m['X'] < xGap) {
				Mx += m['X'];
				My += m['X'];
			}
			else {
				Mx += xGap;
				My += xGap;
			}
		}
		else {
			if (m['X'] < yGap) {
				Mx += m['X'];
				My += m['X'];
			}
			else {
				Mx += yGap;
				My += yGap;
			}
		}
		if (Mx == x && My == y)
			return 1;
		xGap = x - Mx;
		if (xGap > m['R'])
			return 0;
		else {
			Mx = x;
			if (Mx == x && My == y)
				return 1;
		}
		yGap = y - My;
		if (yGap > m['U'])
			return 0;
		else {
			My = y;
			
		}
	}
	return 1;
}


int main() {
	cin >> N;
	cin >> order;
	int x, y;
	for (int i = 0; i < N; i++) {
		if (m[order[i]])
			m[order[i]]++;
		else
			m[order[i]] = 1;
	}
	cin >> K;
	for (int i = 0; i < K; i++) {
		cin >> x >> y;
		cnt += check(x, y);
	}
	cout << cnt;
}

 

 

다 풀고 나서 다른 사람들의 풀이도 보았는데 역시 더 효율적인 방식이 존재했다.

#include <iostream>
using namespace std;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n, q;
	string s;
	cin >> n >> s >> q;

	int r = 0, u = 0, x = 0;
	for(int i = 0; i < n; i++)
	{
		if(s[i] == 'R')
			r++;
		else if(s[i] == 'U')
			u++;
		else
			x++;
	}

	int ans = 0;
	while(q--)
	{
		int a, b;
		cin >> a >> b;

		a--; b--;
		int t = min(x, min(a, b));
		a -= t; b -= t;

		if(a <= r && b <= u)
			ans++;
	}

	cout << ans << '\n';
}