문제

입력

입출력 예시

코드

#include <iostream>
#include <vector>
#include <map>
typedef long long ll;
using namespace std;

int N, M;
vector<vector<ll>> horizon;
vector<vector<ll>> vertical;

map<char, pair<int, int>> dir;

int main() {
	dir.insert({'R', {0, 1}});
	dir.insert({'L', {0, -1}});
	dir.insert({'U', {-1, 0}});
	dir.insert({'D', {1, 0}});
	
	cin >> N >> M;
	horizon = vector<vector<ll>>(N, vector<ll>(N, 0));
	vertical = vector<vector<ll>>(N, vector<ll>(N, 0));
	
	for(int i = 0; i < M; i++) {
		int a, b;
		char c;
		cin >> a >> b >> c;
		--a; --b;
		while(a >= 0 && a < N && b >= 0 && b < N) {
			if(c == 'R' || c == 'L') ++horizon[a][b];
			else ++vertical[a][b];
			a += dir[c].first;
			b += dir[c].second;
		}
	}
	
	ll cnt = 0;
	for(int i = 0; i < N; i++) {
		for(int j = 0; j < N; j++) {
			cnt += horizon[i][j] * vertical[i][j];
		}
	}
	cout << cnt;
	return 0;
}

자료형만 안 틀리면 쉽게 해결할 수 있는 문제.
중첩 점, 즉 교점의 개수를 구하면 되기 때문에 각 칸 당 가로 선의 개수와 세로 선의 개수를 세고, 모든 칸의 가로 선 개수 * 세로 선 개수를 구해주면 된다.

M의 개수가 최대 100,000개여서 int로 할 경우 overflow가 발생할 수 있으므로 long long 타입을 썼다
다른 문제 풀 때도 좀 크다 싶으면 바로 long long으로 풀까..

방향 if문을 많이 쓰고 싶지 않아 map에 방향 별 이동 좌표를 저장해서 풀었다.