[ 구름톤 챌린지 ] 18일차 미션 - 중첩 점

구름톤 챌린지 18일차입니다. 4주차가 시작되면서 점점 구름톤 챌린지도 마무리되어가고 있습니다. 챌린지를 통해 문제 풀이 실력을 향상시킬 수 있으며, 블로그에 학습 일기도 작성하면 추가 보상도 주어지니 관심 있으시면 참여해보시는 것을 추천드립니다.

https://level.goorm.io/l/challenge/goormthon-challenge

구름LEVEL

 

문제

입력 / 출력

풀이 과정

정사각형의 크기는 최대 100, 그리려는 반직선의 개수는 최대 100,000개이므로 단순 브루트포스로 아슬아슬하게 해결이 가능하다.

import sys
input = sys.stdin.readline

n, m = map(int, input().rstrip().split())
maps = [[[0, 0] for _ in range(n)] for _ in range(n)]
# 가로 / 세로

dir_y = {'U':-1, 'D':1, 'L':0, 'R':0}
dir_x = {'U':0, 'D':0, 'L':-1, 'R':1}

for _ in range(m):
	y, x, d = input().rstrip().split()
	y = int(y) - 1; x = int(x) - 1
	
	if d == 'U' or d == 'D': maps[y][x][1] += 1
	else: maps[y][x][0] += 1
	
	ny = y + dir_y[d]
	nx = x + dir_x[d]
	
	while 0 <= ny < n and 0 <= nx < n:
		if d == 'U' or d == 'D': maps[ny][nx][1] += 1
		else: maps[ny][nx][0] += 1
		
		ny += dir_y[d]
		nx += dir_x[d]

result = 0
for i in range(n):
	for j in range(n):
		result += maps[i][j][0] * maps[i][j][1]

print(result)

또한, 세그먼트 트리(?) 로도 풀이가 가능하다. 세로 줄의 정보를 먼저 기록한 뒤 최대 100개의 가로 줄 세그먼트 트리를 만들어 부분합을 구하였다.

#include <stdio.h>
#define N_SIZE 105
#define M_SIZE 100005
typedef long long LL;

LL arr[N_SIZE][N_SIZE] = {0,};
int order[M_SIZE][3];
LL tree[N_SIZE][N_SIZE * 4] = {0,};

void init(int row, int start, int end, int idx) {
	if (start == end) {
		tree[row][idx] = arr[row][start];
		return;
	}
	
	int mid = (start + end) / 2;
	init(row, start, mid, idx * 2);
	init(row, mid + 1, end, idx * 2 + 1);
	tree[row][idx] = tree[row][idx * 2] + tree[row][idx * 2 + 1];
}

LL interval_sum(int row, int start, int end, int idx, int left, int right) {
	if (end < left || right < start) return 0;
	if (left <= start && end <= right) return tree[row][idx];
	
	int mid = (start + end) / 2;
	return interval_sum(row, start, mid, idx * 2, left, right) + interval_sum(row, mid + 1, end, idx * 2 + 1, left, right);
}

int main(void) {
	int n, m;
	scanf("%d %d", &n, &m);
	
	for (int i = 0; i < m; i++) {
		int y, x;
		char d;
		scanf("%d %d %c", &y, &x, &d);
		
		order[i][0] = y;
		order[i][1] = x;
		
		if (d == 'U') order[i][2] = 1;
		else if (d == 'D') order[i][2] = 2;
		else if (d == 'L') order[i][2] = 3;
		else order[i][2] = 4;
	}
	
	for (int i = 0; i < m; i++) {
		if (order[i][2] == 3 || order[i][2] == 4) continue;
		
		if (order[i][2] == 1) {
			for (int k = order[i][0]; k >= 1; k--) arr[k][order[i][1]] += 1;
		}
		else {
			for (int k = order[i][0]; k <= n; k++) arr[k][order[i][1]] += 1;
		}
	}
	for (int i = 1; i <= n; i++) init(i, 1, n, 1);
	
	LL result = 0;
	for (int i = 0; i < m; i++) {
		if (order[i][2] == 1 || order[i][2] == 2) continue;
		
		if (order[i][2] == 3) result += interval_sum(order[i][0], 1, n, 1, 1, order[i][1]);
		else result += interval_sum(order[i][0], 1, n, 1, order[i][1], n);
	}
	printf("%lld", result);
	
	return 0;
}

동적 프로그래밍과 시뮬레이션 문제를 혼합한 문제라고는 하지만... 어떻게 동적 프로그래밍을 대입할지는 감이 오지 않았다. 나중에 해설을 보면서 나의 풀이랑 비교해봐야겠다.