구름톤 챌린지 18일차

문제

https://level.goorm.io/exam/195700/%EC%A4%91%EC%B2%A9-%EC%A0%90/quiz/1

구름LEVEL

 

풀이

dp 문제였고 dp 배열을 어떻게 설정하느냐만 결정되면 매우 쉬운 문제였다.

 

문제에서 중첩되는 점의 개수를 구하라고 되어있다.

중첩되는 점의 개수는 세로와 가로가 교차되는 개수를 의미한다.

즉, 각 칸에서의 세로선의 개수와 가로선의 개수를 구하면 된다.

위의 그림에서 3행2열에서는 가로선이 2개, 세로선이 1개로 2개의 교차점이 생긴다.

이와 같이 세로선의 개수와 가로선의 개수를 구하는 배열을 만들면 된다.

 

세로선의 개수를 구하는 배열 + 가로선의 개수를 구하는 배열을 만들어도 되나 dp 문제이므로 3차원 배열을 이용하여 풀이하였다.

즉, 2개의 이차원 배열을 만드는 풀이는 배열을 다음과 같이 선언하면 된다.

long[][] verMatrix = new int[N + 1][N + 1];
long[][] horMatrix = new int[N + 1][N + 1];

dp문제 같은 경우 이를 하나의 배열에서 관리해주는 3차원 배열을 만든다고 생각하면 된다.

long[][][] dp = new int[2][n+1][n+1];

dp[0]은 세로선의 개수, dp[1]은 가로선의 개수르 구하면 될 것이다.

 

코드

import java.io.*;
import java.util.*;

class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		
		long dp[][][] = new long [2][n+1][n+1];
		
		for(int t=0;t<m;t++){
			st = new StringTokenizer(br.readLine());
			int y = Integer.parseInt(st.nextToken());
			int x = Integer.parseInt(st.nextToken());
			String d = st.nextToken();
			
			if(d.equals("U")){
				for(int i=y;i>=0;i--){
					dp[0][i][x] += 1;
				}
			}
			else if(d.equals("D")){
				for(int i=y;i<=n;i++){
					dp[0][i][x] += 1;
				}
			}
			else if(d.equals("L")){
				for(int i=x;i>=0;i--){
					dp[1][y][i] += 1;
				}
			}
			else{
				for(int i=x;i<=n;i++){
					dp[1][y][i] += 1;
				}
			}
		}
		
		long result = 0;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				result += dp[0][i][j] * dp[1][i][j];
			}
		}
	
		System.out.println(result);
	}
}