[코드트리 챌린지] 1주차 - 최고의 33위치

 

문제링크

https://www.codetree.ai/cote/13/problems/best-place-of-33?&utm_source=clipboard&utm_medium=text 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

핵심

1. 시간복잡도 : MAX_N = 20 → O(9N^2) : 브루트포스(완전탐색)

2. 격자 내 판단 : in_range(inRange)함수로 판단

3. For문으로 구현

---

코드(Python)

n = int(input())
# 왼쪽상단 기준
board =[list(map(int, input().split())) for _ in range(n)]
# 시간복잡도 : O(((N * N)- @) * 3*3) => O(9N^2)
# 격자 내 체크
def in_range(r, c):
    return 0 <= r + 2 < n and 0 <= c + 2 < n

ans = 0
for r in range(n):
    for c in range(n):
        cnt = 0
        if in_range(r, c):
            # print("여기 좌표", r, c)
            for i in range(3):
                for j in range(3):
                    if board[r + i][c + j] == 1:
                        cnt += 1
            ans = max(ans, cnt)

print(ans)

---

코드(Java)

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

public class Main {
    private static int N;
    private static int MAX_N = 20;
    private static int[][] board = new int[MAX_N][MAX_N];

    private static boolean isRange(int r, int c, int N){
        return 0 <= r + 2 && r + 2 < N &&  0 <= c + 2 && c + 2 < N;
    }
    public static int getMaxCount(int[][] board, int N) {
        int ans = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                int cnt = 0;
                if (isRange(i, j, N)) {
                    for (int r = 0; r < 3; r++) {
                        for (int c = 0; c < 3; c++) {
                            if (board[i + r][j + c] == 1) {
                                cnt++;
                            }
                        }
                    }
                    ans = Math.max(ans, cnt);
                }
            }
        }
        return ans;
    }

    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());
        for(int i = 0; i < N; i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < N; j++){
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        System.out.print(getMaxCount(board, N));
    }
}