728x90
반응형
문제링크
https://www.codetree.ai/missions/2/problems/tromino?&utm_source=clipboard&utm_medium=text
코드트리 | 코딩테스트 준비를 위한 알고리즘 정석
국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.
www.codetree.ai
1. 핵심
- 주어진 블록의 가능한 경우의 수 모두 적고 순회하기
- 주어진 블록의 공통 이차원 배열을 선정하고 왼쪽 상단에 밀착!
- 왼쪽상단에 밀착해야 주어진 격자 내에 가능한 부분을 모두 파악 가능
2. 코드(Java)
import java.util.*;
import java.io.*;
public class Main {
public static int MAX = 200;
public static final int[][] board = new int[MAX][MAX];
public static int N, M;
// 총 6개의 배열이 모두 포함되게 하는 공통된 이차원 배열을 사용하는 것이 깔끔하다!
// 2x2 와 3x1 이 있으므로 3x3이 공통된 이차원 배열이라고 할 수 있다.
// 공통된 이차원 배열의 왼쪽 상단에 밀착! -> 밀착시키지 않으면 보지 못하는 곳 존재.
public static int[][][] possibleShapes = new int[][][]{
{{1,1,0},
{1,0,0},
{0,0,0}},
{{1,1,0},
{0,1,0},
{0,0,0}},
{{0,1,0},
{1,1,0},
{0,0,0}},
{{1,0,0},
{1,1,0},
{0,0,0}},
{{1,1,1},
{0,0,0},
{0,0,0}},
{{1,0,0},
{1,0,0},
{1,0,0}},
};
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer inputNM = new StringTokenizer(br.readLine());
N = Integer.parseInt(inputNM.nextToken());
M = Integer.parseInt(inputNM.nextToken());
for(int r = 0; r < N; r++){
StringTokenizer row = new StringTokenizer(br.readLine());
for (int c = 0; c < M; c++){
board[r][c] = Integer.parseInt(row.nextToken());
}
}
int res = 0;
for(int r = 0; r < N; r++){
for(int c = 0; c < M; c++){
res = Math.max(res, getMaxSum(r, c));
}
}
System.out.println(res);
}
public static int getMaxSum(int r, int c){
int maxSumVal = 0;
for (int i = 0; i < 6; i++){
int sum = 0;
boolean isRange = true;
for(int dr = 0; dr < 3; dr++){
for (int dc = 0; dc < 3; dc++){
if(possibleShapes[i][dr][dc] == 0){
continue;
}
// 1인데 현재(r,c)기준에서 n,m보다 크거나 같으면 격자밖을 의미함.
if(r + dr >= N || c + dc >= M){
isRange = false;
}
else{
sum += board[r + dr][c + dc];
}
}
if(isRange){
maxSumVal = Math.max(maxSumVal, sum);
}
}
}
return maxSumVal;
}
}
728x90
반응형
'PS > 코드트리' 카테고리의 다른 글
[백트래킹] K개 중 하나를 N번 선택하기(Conditional) / 1차원 윷놀이 (1) | 2024.01.16 |
---|---|
[백트래킹] K개 중 하나를 N번 선택하기(Simple) / 강력한 폭발 (1) | 2024.01.14 |
[코드트리 챌린지] 8주차 - 그리디 (0) | 2023.10.30 |
[코드트리 챌린지] 7주차 - 시뮬레이션(격자 안에서 단일 객체를 이동) (1) | 2023.10.23 |
[코드트리 챌린지] 6주차 - 시간최적화(Priority Queue) (0) | 2023.10.16 |