[코드트리 챌린지] 2주차 - Simulation (2)

★ 핵심 : 격자 안에서의 완전탐색

1. 유형 : 모든 경우의 수 판단

2. 시간복잡도 계산 필수 : 보편적으로 시간복잡도가 1억이 넘어가면 시간초과날 확률이 높다.

---

문제링크

https://www.codetree.ai/cote/13/problems/tromino?&utm_source=clipboard&utm_medium=text' 

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

핵심

1. 2가지 블록의 총 경우의 수 : 6가지( ㅡ모양, ㅣ모양, ㄱ모양, 반대ㄱ모양, ㄴ모양, 반대 ㄴ 모양)

 2. 반대모양 구할 때 모양을 돌리지 말고 점수판자체를 반대로 하는 것이 훨씬 편리하다.

board = [list(map(int, input().split())) for _ in range(n)]
reverse_borad = [row[::-1] for row in board]

---

코드(Python)

# 시간복잡도
# O(N * M)
n, m = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)]
reverse_borad = [row[::-1] for row in board]
# ㅡ 모양
def f1_1(n, m, board):
    sum_val = 0
    for r in range(n):
        for c in range(m - 3 + 1):
            sum_val = max(sum_val, board[r][c] + board[r][c + 1] + board[r][c + 2])
    return sum_val
res1_1 = f1_1(n, m, board)
# ㅣ 모양
def f1_2(n, m, board):
    sum_val = 0
    for r in range(n - 3 + 1):
        for c in range(m):
            sum_val = max(sum_val, board[r][c] + board[r + 1][c] + board[r + 2][c])
    return sum_val
res1_2 = f1_2(n, m, board)
# ㄴ 모양 
def f2_1(n, m, board):
    sum_val = 0
    for r in range(n - 2 + 1):
        for c in range(m - 2 + 1):
            sum_val = max(sum_val, board[r][c] + board[r + 1][c] + board[r + 1][c + 1])
    return sum_val
res2_1 = f2_1(n, m, board)
res2_1_R = f2_1(n, m, reverse_borad)
# ㄱ 모양
def f2_2(n, m, board):
    sum_val = 0
    for r in range(n - 2 + 1):
        for c in range(m - 2 + 1):
            sum_val = max(sum_val, board[r][c] + board[r][c + 1] + board[r + 1][c + 1])
    return sum_val
res2_2 = f2_2(n, m, board)
res2_2_R = f2_2(n, m, reverse_borad)

print(max(res1_1, res1_2, res2_1, res2_1_R, res2_2, res2_2_R))

---

코드(Java)

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

public class Main {
    public static int n, m, sum_val, MAX_N = 200, MAX_M = 200;
    public static int[][] board = new int[MAX_N][MAX_M];
    public static int[][] reverseBoard = new int[MAX_N][MAX_M];
    // - 모양
    public static int f1_1(int n, int m, int[][]board){
        sum_val = 0;
        for(int r = 0; r < n; r++){
            for(int c = 0; c < m - 3 + 1; c++){
                sum_val = Math.max(sum_val, board[r][c] + board[r][c + 1] + board[r][c + 2]);
            }
        }
        return sum_val;
    }
    // l 모양
    public static int f1_2(int n, int m, int[][]board){
        sum_val = 0;
        for(int r = 0; r < n - 3 + 1; r++){
            for(int c = 0; c < m; c++ ){
                sum_val = Math.max(sum_val, board[r][c] + board[r + 1][c] + board[r + 2][c]);
            }
        }
        return sum_val;
    }
    //ㄴ모양
    public static int f2_1(int n, int m, int[][]board){
        sum_val = 0;
        for(int r = 0; r < n - 2 + 1; r++){
            for(int c = 0; c < m - 2 + 1; c++ ){
                sum_val = Math.max(sum_val, board[r][c] + board[r + 1][c] + board[r + 1][c + 1]);
            }
        }
        return sum_val;
    }
    // ㄱ모양
    public static int f2_2(int n, int m, int[][]board){
        sum_val = 0;
        for(int r = 0; r < n - 2 + 1; r++){
            for(int c = 0; c < m - 2 + 1; c++ ){
                sum_val = Math.max(sum_val, board[r][c] + board[r][c + 1] + board[r + 1][c + 1]);
            }
        }
        return sum_val;
    }

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

        for(int i = 0; i < n; i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < m; j++){
                String k = st.nextToken();
                board[i][j] = Integer.parseInt(k);
                reverseBoard[i][m - j - 1] = Integer.parseInt(k);
            }
        }
        int[] results = new int[6];
        results[0] = f1_1(n, m, board);
        results[1] = f1_2(n, m, board);
        results[2] = f2_1(n, m, board);
        results[3] = f2_1(n, m, reverseBoard);
        results[4] = f2_2(n, m, board);
        results[5] = f2_2(n, m, reverseBoard);

        int maxResult = 0;
        for (int result : results) {
            maxResult = Math.max(maxResult, result);
        }
        System.out.print(maxResult);
    }
}

---

◎관련문제

 

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

14500번: 테트로미노

 

※ 실력진단