골랜디 #5 14500번
Published at: 2025-03-24
Last modified at: 2025-03-24
안녕하세요 한라나입니다.
오늘은 사실 깜빡하고 있었습니다.
근데 자려고 누워서 코찜질을 하다 보니 골랜디 생각이 나는거에요?
던질까 생각도 해봤는데 작심사일은 좀 아닌 것 같아서 다시 일어났습니다.
일어나는 김에 날짜 표시도 00:00:00은 없애버렸습니다.
브루트포스 구현이라니…. 어제 살살 해줬다고 오늘 뚜들겨 패네요.
브루트포스인 만큼 그냥 ‘다’ 해 보면 됩니다. 다만 어떤걸 해봐야 하는지는 알아야겠죠.
모양이 다른 테트로미노는 총 19개가 있습니다. 직선이 두 개, 정사각형은 한 개, 그리고 L 4가지 방향, J 4가지 방향, ㅗ 4가지 방향과 s, z 각각 두 가지 방향입니다.
저는 직선, 정사각형은 따로 하고, 2*3모양과 3*2모양을 분류해서 했습니다.
각각 8가지씩 있는데요, 네 가지 숫자를 더하는건 항상 똑같으니까 왼쪽 위 칸을 기준으로 어느 위치에 있는 네 가지 칸을 더해야 하는지 배열을 만들었습니다.
int shapes2by3[8][4][2] = {
{ {0, 0}, {0, 1}, {0, 2}, {1, 1} },
{ {1, 0}, {1, 1}, {1, 2}, {0, 1} },
{ {0, 0}, {0, 1}, {0, 2}, {1, 0} },
{ {1, 0}, {1, 1}, {1, 2}, {0, 2} },
{ {0, 0}, {1, 0}, {1, 1}, {1, 2} },
{ {0, 0}, {0, 1}, {0, 2}, {1, 2} },
{ {1, 0}, {1, 1}, {0, 1}, {0, 2} },
{ {0, 0}, {0, 1}, {1, 1}, {1, 2} }
};
int shapes3by2[8][4][2] = {
{ {0, 1}, {1, 1}, {2, 1}, {1, 0} },
{ {0, 0}, {1, 0}, {2, 0}, {1, 1} },
{ {0, 0}, {1, 0}, {2, 0}, {2, 1} },
{ {0, 0}, {0, 1}, {1, 1}, {2, 1} },
{ {2, 0}, {0, 1}, {1, 1}, {2, 1} },
{ {0, 0}, {1, 0}, {2, 0}, {0, 1} },
{ {2, 0}, {1, 0}, {1, 1}, {0, 1} },
{ {0, 0}, {1, 0}, {1, 1}, {2, 1} }
};
완전… 노가다죠… 허…
그 다음부터는 ‘왼쪽 위 지점’으로 가능한 모든 점에 대해 저것들을 사용해서 네 가지 숫자를 더한 값이 기존 ans보다 크면 바꾸고를 끝까지 반복하면 됩니다.
for(i=0;i<n-1;i++) {
for(j=0;j<m-2;j++) {
int k;
for(k=0;k<8;k++) {
ans = max(ans, numbers[i+shapes2by3[k][0][0]][j+shapes2by3[k][0][1]]+numbers[i+shapes2by3[k][1][0]][j+shapes2by3[k][1][1]]+numbers[i+shapes2by3[k][2][0]][j+shapes2by3[k][2][1]]+numbers[i+shapes2by3[k][3][0]][j+shapes2by3[k][3][1]]);
}
}
}
//이건 2*3일때
이거보다 더 나은 방법이 있을런지… 있어도 전 안 찾을래요. 미쳐버린거냐.
어쩌면 골드의 기준은 어려움이라기보다는 뭣같음이 아닐까 생각이 드는 요즘입니다. 이걸 2만 6천 800명이나 풀었어요. 그것도 놀랍네요.
감사합니다.
전체 코드
#include <stdio.h>
//using namespace std;
int max(int a, int b) {
if(a>b) return a;
else return b;
}
int main() {
int n, m;
scanf("%d %d", &n, &m);
int i, j;
int numbers[550][550];
for(i=0;i<n;i++) {
for(j=0;j<m;j++) {
scanf("%d", &numbers[i][j]);
}
}
int ans = 0;
//straight
for(i=0;i<n-3;i++) {
for(j=0;j<m;j++) {
ans = max(ans, numbers[i][j]+numbers[i+1][j]+numbers[i+2][j]+numbers[i+3][j]);
}
}
for(i=0;i<n;i++) {
for(j=0;j<m-3;j++) {
ans = max(ans, numbers[i][j]+numbers[i][j+1]+numbers[i][j+2]+numbers[i][j+3]);
}
}
//square
for(i=0;i<n-1;i++) {
for(j=0;j<m-1;j++) {
ans = max(ans, numbers[i][j]+numbers[i][j+1]+numbers[i+1][j]+numbers[i+1][j+1]);
}
}
//2*3
int shapes2by3[8][4][2] = {
{ {0, 0}, {0, 1}, {0, 2}, {1, 1} },
{ {1, 0}, {1, 1}, {1, 2}, {0, 1} },
{ {0, 0}, {0, 1}, {0, 2}, {1, 0} },
{ {1, 0}, {1, 1}, {1, 2}, {0, 2} },
{ {0, 0}, {1, 0}, {1, 1}, {1, 2} },
{ {0, 0}, {0, 1}, {0, 2}, {1, 2} },
{ {1, 0}, {1, 1}, {0, 1}, {0, 2} },
{ {0, 0}, {0, 1}, {1, 1}, {1, 2} }
};
for(i=0;i<n-1;i++) {
for(j=0;j<m-2;j++) {
int k;
for(k=0;k<8;k++) {
ans = max(ans, numbers[i+shapes2by3[k][0][0]][j+shapes2by3[k][0][1]]+numbers[i+shapes2by3[k][1][0]][j+shapes2by3[k][1][1]]+numbers[i+shapes2by3[k][2][0]][j+shapes2by3[k][2][1]]+numbers[i+shapes2by3[k][3][0]][j+shapes2by3[k][3][1]]);
}
}
}
//3*2
int shapes3by2[8][4][2] = {
{ {0, 1}, {1, 1}, {2, 1}, {1, 0} },
{ {0, 0}, {1, 0}, {2, 0}, {1, 1} },
{ {0, 0}, {1, 0}, {2, 0}, {2, 1} },
{ {0, 0}, {0, 1}, {1, 1}, {2, 1} },
{ {2, 0}, {0, 1}, {1, 1}, {2, 1} },
{ {0, 0}, {1, 0}, {2, 0}, {0, 1} },
{ {2, 0}, {1, 0}, {1, 1}, {0, 1} },
{ {0, 0}, {1, 0}, {1, 1}, {2, 1} }
};
for(i=0;i<n-2;i++) {
for(j=0;j<m-1;j++) {
int k;
for(k=0;k<8;k++) {
ans = max(ans, numbers[i+shapes3by2[k][0][0]][j+shapes3by2[k][0][1]]+numbers[i+shapes3by2[k][1][0]][j+shapes3by2[k][1][1]]+numbers[i+shapes3by2[k][2][0]][j+shapes3by2[k][2][1]]+numbers[i+shapes3by2[k][3][0]][j+shapes3by2[k][3][1]]);
}
}
}
printf("%d", ans);
return 0;
}
여기서 {{ 쓰면 오류나네요… 이스케이프 시켜줘야하네요 다…
아니 근데 생각해보니까 다 닫혀 있잖아 근데 왜 안닫혀있다고 오류가 나