[백준 1460] 진욱이의 농장 - JAVA

https://www.acmicpc.net/problem/1460

 

 

접근이 어려워서 포스팅 보고 시작했다.

https://magentino.tistory.com/95

 

 

1.  씨앗을 최대 두 종류 포함했는지 판별

 

농장을 범위를 선택하고, 포함된 과일 씨앗를 체크한다. X

씨앗을 두 개 뽑은채로 농장 범위를 선택한다. O

 

m[i][j]가 두 개의 씨앗 중 하나라면 dp[i][j] = 1로 놓는다.

그러면 dp가 0-1 값으로 초기화된다.

 

2. 씨앗 두 개씩 뽑기

씨앗은 8가지 밖에 없고, 순서도 상관 없으므로 조합으로 뽑는다.

 

 

3. dp 도출

dp[i][j] = 좌표 (0,0)부터 (i,j)까지 고려했을 때, 준규가 가져갈 수 있는 농장의 최대 길이

 

dp[i][j] = 0이라면, 0번 씨앗 or 선택하지 않은 씨앗이 심어져있으므로 continue한다.

 

0이 아니라면, 식을 다음과 같이 놓는다.

dp[i][j] = Math.min(dp[i - 1][j], Math.min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;

 

세 값은 각각 세로, 가로, 대각선 방향으로 보장된 농장의 최대 길이를 의미한다.

(대각선 길이가 더 길어야함을 굳이 고려한다면 최대 칸 수)

 

구하려는 것은 정사각형이므로 세 가지 모두 보장하기 위해 최솟값을 뽑는다. 여기에 i,j번째 농장이 추가되므로 1을 더해준다.

 

// 씨앗 3과 5를 뽑는 경우

 map           dp(init)       dp(최종)
3 3 5 5        1 1 1 1        1 1 1 1
3 3 5 5        1 1 1 1        1 2 2 2
0 5 5 5   ->   0 1 1 1   ->   0 1 2 3
2 0 4 4        0 0 0 0        0 0 0 0

 

 

제출 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

class Main {

  static void solve(int a, int b) {

    int[][] dp = new int[N][N];

    for (int i = 0; i < N; i++) {
      for (int j = 0; j < N; j++) {
        if (m[i][j] == a || m[i][j] == b) {
          dp[i][j] = 1;
        }
      }
    }

    for (int i = 1; i < N; i++) {
      for (int j = 1; j < N; j++) {

        if (dp[i][j] == 0) {
          continue;
        }
        dp[i][j] = Math.min(dp[i - 1][j], Math.min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;
      }
    }

    for (int[] row : dp) {
      for (int e : row) {
        max = Math.max(max, e);
      }
    }

  }

  static int N, max, m[][];

  public static void main(String[] args) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());

    N = Integer.parseInt(st.nextToken());
    int M = Integer.parseInt(st.nextToken());

    m = new int[N][N];

    for (int i = 0; i < M; i++) {
      st = new StringTokenizer(br.readLine());

      int x = Integer.parseInt(st.nextToken());
      int y = Integer.parseInt(st.nextToken());
      int l = Integer.parseInt(st.nextToken());
      int v = Integer.parseInt(st.nextToken());

      for (int c = x; c < x + l; c++) {
        for (int r = y; r < y + l; r++) {
          m[r][c] = v;
        }
      }
    }

    for (int i = 1; i <= 7; i++) {
      for (int j = i + 1; j <= 7; j++) {
        solve(i, j);
      }
    }

    System.out.println(max * max);
  }
}