구름톤 챌린지 4주 차 문제 18 학습 일기

https://goor.me/wDFSjuDNjzXTTqH4A

​

 

 

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());

        Pair[][] arr = new Pair[n + 1][n + 1];
        for(int i=0; i<=n; i++){
            for(int j=0; j<=n; j++){
                arr[i][j] = new Pair();
            }
        }

        for(int i=0; i<m; i++){
            st = new StringTokenizer(br.readLine());
            int y = Integer.parseInt(st.nextToken());
            int x = Integer.parseInt(st.nextToken());
            char c= st.nextToken().charAt(0);
            
            if(c == 'R'){
                for(int k=x;k<=n;k++)
                    arr[y][k].x += 1;
                
            } else if(c == 'L'){
                for(int k=1;k<=x;k++)
                    arr[y][k].x += 1;
                
            } else if(c == 'D'){
                for(int k=y;k<=n;k++)
                    arr[k][x].y += 1;
                
            } else if(c == 'U'){
                for(int k=1;k<=y;k++)
                    arr[k][x].y += 1;
             }
         }

         long ans=0;

         for(int i=1;i<=n;i++){
             for(int j=1;j<=n;j++){
                 ans+=arr[i][j].x*arr[i][j].y;
             } 
         }

         System.out.println(ans);
     }

     static class Pair{
         long y;
         long x;

         public Pair(){
             this.y=0;
             this.x=0;
          } 
      }
}

 

이 문제는 꽤 재밌었다.

탐색 + dp 문제

세로선 가로선이 교차하는 점의 개수를 구하면 되는데, 가로선끼리 세로선끼리는 겹치지 않는다.

그래서 2차원 배열로 맵을 만들고 각 칸마다 세로선과 가로선의 개수를 기록해준다.

이후에 세로선 개수 X 가로선 개수 를 누적합하면 정답이 나온다.

아까 공개된 정답 코드 봤는데 완벽하게 이해하지는 못했고 아마 비슷한 접근인 듯 한데, 정답 코드는 굳이 3차원 배열 써서 조건문 돌 때 마다 누적합까지 해줬고

나는 pair를 2차원 배열에 저장해서 세로선과 가로선을 기록했다.

​

이렇게 해서 네이버 페이 10000원을 벌었다.