구름톤 챌린지 - 18일차

문제 이해

N x N 형태의 정사각형이 주어지고 M개의 반직선을 그린 뒤 교차하는 점의 개수를 세는 문제.

 

 

아이디어 구상

첫번째 시도

dx, dy 테크닉을 사용하여 범위 안에서 한쪽 방향으로 끝까지 체크하도록 시도했다.

결과 : FAIL

이유 : 단순하게 x,y를 찍어버리게 되면 길이가 1 x 1인 경우 예외적인 케이스가 발생하게 됨.

두번째 시도

가로와 세로를 나눠서 L, R일 때와 U, D를 각각 체크시킨 후 

반복문을 돌면서 해당 위치에 있는 값을 곱해주면 해당 위치에 얼마만큼 교차해있는지 알 수 있을 것이라 추정.

결과 : SUCCESS

코드

#include <iostream>
#include <string>
using namespace std;
#define MX 105
int n, m;
long long a[MX][MX], b[MX][MX];
//D U L R
int dx[] = {0,0,-1,1};
int dy[] = {1,-1,0,0};

int inRange(int x, int y){
	return 0 < x && x <= n && 0 < y && y <= n;
}
int main() {
	cin >> n >> m;
	int x,y;
	string d;
	for(int i = 0; i < m; i++){
		cin >> y >> x >> d;
		int dir = 0;
		if(d == "D") dir = 0;
		else if(d == "U") dir = 1;
		else if(d == "L") dir = 2;
		else if(d == "R") dir = 3;
		while(inRange(y,x)){
			if(d == "L" || d == "R") a[y][x]++;
			else b[y][x]++;
			x += dx[dir];
			y += dy[dir];
		}//j
	}//i
	long long cnt = 0;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			cnt += a[i][j] * b[i][j];
			//cout << a[i][j] << " ";
		}
		//cout << "\n";
	}
	cout << cnt;
	return 0;
}

후기

단순하게 추정짓고 문제를 풀게 되면 절대 안된다고 느꼈음.

분석을 확실하게 끝내고 구현을 해야 함.

예를 들어 데이터 값의 범위가 어떻게 되는지, 탐색 범위가 어떻게 되는지, 방문 체크 여부를 사용할 것인지 등이 있다.