[Algorithm] 99클럽 코테 스터디 12일차 TIL | 백준_숫자 정사각형(1051번)

2025. 2. 4. 13:24·Algorithm

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


반례를 찾느라 진빠졌던 문제다;

완전탐색이라고 생각하고 풀면 어렵지 않다.

 

왼쪽 위 부터 오른쪽 아래까지 모두 검사하며 정사각형을 구한다.

배열로 치면

arr[0][0]~arr[N-1][M-1] 까지

 

만약 세로줄에서 같은 수를 찾았다면 가로줄에서 같은 값이 있는지 찾는다.

이렇게 총 4개의 점에 대해 검사를 해야한다.

public static int rectangle(int a, int b){
    int n = arr[a][b];
    int h,w;
    int area = 0;

    for(int i = a+1; i < N; i++){
        if(arr[i][b] == n){
            h = i-a+1;
            for(int j = b+1; j < M; j++){
                if(arr[a][j] == n && arr[i][j] == n){
                    w = j-b+1;
                    if(h==w){
                        area = Math.max(area, h*w);
                    }
                }
            }
        }
    }
    return area;
}

arr[i][j] == n 부분을 빼먹고 맞는데 왜 틀리지? 라고 생각했으나

역시 컴퓨터는 나보다 정확하다

내가 놓친 반례는 아래의 경우의 수다.

3 3
222
223
223

 

전체코드

import java.util.*;
import java.io.*;
class Main{
    static int N,M;
    static int[][] arr;
    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());
        M = Integer.parseInt(st.nextToken());
        arr = new int[N][M];
        for(int i = 0; i < N; i++){
            String str = br.readLine();
            for(int j = 0; j < M; j++){
                arr[i][j] = str.charAt(j) - '0';
            }
        }
        int max = 1;
        for(int i = 0; i < N; i++){
            for(int j = 0; j < M; j++){
                max = Math.max(max, rectangle(i,j));
            }
        }
        System.out.println(max);
    }
    public static int rectangle(int a, int b){
        int n = arr[a][b];
        int h,w;
        int area = 0;

        for(int i = a+1; i < N; i++){
            if(arr[i][b] == n){
                h = i-a+1;
                for(int j = b+1; j < M; j++){
                    if(arr[a][j] == n && arr[i][j] == n){
                        w = j-b+1;
                        if(h==w){
                            area = Math.max(area, h*w);
                        }
                    }
                }
            }
        }
        return area;
    }
}

 

 

'Algorithm' 카테고리의 다른 글

[Algorithm] 99클럽 코테 스터디 14일차 TIL | 백준_오목(2615번)  (0) 2025.02.06
[Algorithm] 99클럽 코테 스터디 13일차 TIL | 백준_부등호(2529번)  (0) 2025.02.05
[Algorithm] 99클럽 코테 스터디 11일차 TIL | 백준_체스판 다시 칠하기(1018번)  (0) 2025.02.03
[Algorithm] 99클럽 코테 스터디 10일차 TIL | 백준_빙산(2573번)  (4) 2025.01.24
[Algorithm] 99클럽 코테 스터디 9일차 TIL | 백준_이분 그래프(1707번)  (0) 2025.01.23
'Algorithm' 카테고리의 다른 글
  • [Algorithm] 99클럽 코테 스터디 14일차 TIL | 백준_오목(2615번)
  • [Algorithm] 99클럽 코테 스터디 13일차 TIL | 백준_부등호(2529번)
  • [Algorithm] 99클럽 코테 스터디 11일차 TIL | 백준_체스판 다시 칠하기(1018번)
  • [Algorithm] 99클럽 코테 스터디 10일차 TIL | 백준_빙산(2573번)
dev_ajrqkq
dev_ajrqkq
알고리즘 천재가 될 거야
  • dev_ajrqkq
    기록이 자산이다
    dev_ajrqkq
  • 전체
    오늘
    어제
    • 분류 전체보기 (159) N
      • Front-end (0)
      • Back-end (4)
        • Spring (1)
        • Java (8)
      • CS (9)
        • 데이터베이스 (5)
        • 네트워크 (4)
      • Algorithm (88) N
      • 이것저것 (0)
      • 버그잡기 (1)
      • TIL (37)
      • 후기 (3)
      • 취준 (0)
  • 블로그 메뉴

    • 링크

    • 공지사항

    • 인기 글

    • 태그

      오블완
      환급챌린지
      습관형성
      오공완
      Til
      TypeScript
      개발자취업
      패스트캠퍼스
      직장인자기계발
      티스토리챌린지
      패스트캠퍼스후기
      항해99
      99클럽
      코딩테스트준비
    • 최근 댓글

    • 최근 글

    • hELLO· Designed By정상우.v4.10.2
    dev_ajrqkq
    [Algorithm] 99클럽 코테 스터디 12일차 TIL | 백준_숫자 정사각형(1051번)
    상단으로

    티스토리툴바