혜윤이는 최근에 다양한 대회를 참여하면서 노트북에 붙일 수 있는 스티커들을 많이 받았다. 스티커는 아래와 같이 사각 모눈종이 위에 인쇄되어 있으며, 스티커의 각 칸은 상하좌우로 모두 연결되어 있다. 또한 모눈종이의 크기는 스티커의 크기에 꼭 맞아서, 상하좌우에 스티커가 포함되지 않는 불필요한 행이나 열이 존재하지 않는다.
아래는 올바른 모눈종이의 예시이다. 주황색 칸은 스티커가 붙은 칸을, 하얀색 칸은 스티커가 붙지 않은 칸을 나타낸다.
반면 아래는 올바르지 않은 모눈종이의 예시이다. 첫 번째는 윗쪽에 불필요한 행이 있고, 두 번째는 왼쪽에 불필요한 열이 있다. 그리고 세 번째는 스티커의 각 칸이 상하좌우로 모두 연결되어 있지 않다.
혜윤이는 자신의 노트북에 이 스티커들을 붙이기로 했다. 혜윤이의 노트북은 마침 직사각형 모양이고, 스티커가 인쇄된 모눈종이와 같은 간격으로 격자가 그려져 있다. 혜윤이는 스티커들을 먼저 받았던 것부터 차례대로 격자에 맞춰서 붙이려고 한다.
혜윤이가 스티커를 붙이는 방법은 다음과 같다.
스티커를 회전시키지 않고 모눈종이에서 떼어낸다.
다른 스티커와 겹치거나 노트북을 벗어나지 않으면서 스티커를 붙일 수 있는 위치를 찾는다. 혜윤이는 노트북의 위쪽부터 스티커를 채워 나가려고 해서, 스티커를 붙일 수 있는 위치가 여러 곳 있다면 가장 위쪽의 위치를 선택한다. 가장 위쪽에 해당하는 위치도 여러 곳이 있다면 그중에서 가장 왼쪽의 위치를 선택한다.
선택한 위치에 스티커를 붙인다. 만약 스티커를 붙일 수 있는 위치가 전혀 없어서 스티커를 붙이지 못했다면, 스티커를 시계 방향으로 90도 회전한 뒤 2번 과정을 반복한다.
위의 과정을 네 번 반복해서 스티커를 0도, 90도, 180도, 270도 회전시켜 봤음에도 스티커를 붙이지 못했다면 해당 스티커를 붙이지 않고 버린다.
아래의 예시를 통해 스티커를 붙이는 과정을 이해해보자. 노트북은 세로 5칸, 가로 4칸 크기이고, 혜윤이가 가지고 있는 스티커들은 아래와 같다. 왼쪽에서 오른쪽 순으로 스티커를 붙일 것이다.
첫 번째 스티커는 회전 없이 온전히 붙일 수 있는 공간이 아래와 같이 6곳이 있다.
이 중에서 가장 위쪽의 위치, 가능한 가장 위쪽의 위치가 여러 개이면 그 중에서 가장 왼쪽의 위치는 첫 번째이다. 스티커를 붙인 후 노트북의 모양은 아래와 같다.
두 번째 스티커는 회전 없이 온전히 붙일 수 있는 공간이 없다. 그러나 시계 방향으로 90도 회전한 후에는 붙일 수 있는 공간이 1개 생긴다. 해당 공간에 스티커를 붙인 후 노트북의 모양은 아래와 같다.
세 번째 스티커는 스티커를 시계방향으로 0, 90, 180, 270도 회전시킨 모양에 대해 전부 확인을 해도 스티커를 붙일 수 있는 공간이 없다. 그러므로 해당 스티커를 붙이지 않고 버린다.
네 번째 스티커는 스티커를 시계방향으로 0, 90, 180도 회전 시킨 모양에 대해 온전히 붙일 수 있는 공간이 없다. 그러나 시계 방향으로 270도 회전한 후에는 공간이 1개 생긴다. 스티커를 붙인 후 노트북의 모양은 아래와 같다. 최종적으로 노트북의 18칸이 스티커로 채워졌다.
혜윤이는 스티커를 다 붙인 후의 노트북의 모습이 궁금해졌다. 노트북의 크기와 스티커들이 주어졌을 때 스티커들을 차례대로 붙이고 난 후 노트북에서 몇 개의 칸이 채워졌는지 구해보자.
입력
첫째 줄에 노트북의 세로와 가로 길이를 나타내는 N(1 ≤ N ≤ 40)과 M(1 ≤ M ≤ 40) 그리고 스티커의 개수 K(1 ≤ K ≤ 100)이 한 칸의 빈칸을 사이에 두고 주어진다. 그 다음 줄부터는 K개의 스티커들에 대한 정보가 주어진다. 각 스티커는 아래와 같은 형식으로 주어진다. 먼저 i번째 스티커가 인쇄된 모눈종이의 행의 개수와 열의 개수를 나타내는 Ri(1 ≤ Ri ≤ 10)와 Ci(1 ≤ Ci ≤ 10)가 한 칸의 빈칸을 사이에 두고 주어진다. 다음 Ri개의 줄에는 각 줄마다 모눈종이의 각 행을 나타내는 Ci개의 정수가 한 개의 빈칸을 사이에 두고 주어진다. 각 칸에 들어가는 값은 0, 1이다. 0은 스티커가 붙지 않은 칸을, 1은 스티커가 붙은 칸을 의미한다. 문제에서 설명한 것과 같이 스티커는 모두 올바른 모눈종이에 인쇄되어 있다. 구체적으로 스티커의 각 칸은 상하좌우로 모두 연결되어 있고, 모눈종이의 크기는 스티커의 크기에 꼭 맞아서 상하좌우에 스티커에 전혀 포함되지 않는 불필요한 행이나 열이 존재하지 않는다.
출력
첫째 줄에 주어진 스티커들을 차례대로 붙였을 때 노트북에서 스티커가 붙은 칸의 수를 출력한다.
풀이
무식함의 끝으로 풀었다. 2차원 배열 노트북 / x크기,y크기,모눈종이 위 스티커, 스티커 칸수, 스티커 사용여부의 속성을 가진 스티커 클래스를 선언하였다. 이후 스티커들로 이루어진 배열을 선언하고, 4중 for문으로 노트북의 맨 윗칸부터 스티커를 붙일 수 있나 찾아가다가 안되면 90도씩 회전하는 방식으로 했다. 스티커를 붙이는 함수는 먼저 노트북 배열을 깊은 복사를 해서 복사본을 만들고, 시작점에서의 노트북과 스티커의 크기를 계산 한 뒤, 회전에 맞게 for문을 돌며 복사본노트북에 스티커의 값을 더해주었다. 만약 스티커가 겹쳐진다면, 스티커를 붙이는 것이 불가능 한 거싱므로 그대로 기존의 노트북 반환. 회전은 90 = (x, rt_y-y-1) / 180 = (rt_y -y -1 , rt_x - x -1) / 270 = (rt_x-x-1,y) 이렇게 했다. 끝까지 다 붙여봤을 때 겹치는 부분이 없으면, 깊은 복사를 한 복사본을 반납한다. 이때 스티커 클래스에 사용되었는지 함수를 참으로 바꿔준다. 이후에 이 스티커 클래스에 사용여부로 for문을 탈출하고, 스티커 칸수 값을 계산하였다.
코드
import java.io.IOException;
public class Main {
static class sticker{
int x;
int y;
int size[][];
int num;
boolean used;
public sticker(int y, int x) {
this.y = y;
this.x = x;
size = new int[y][x];
used = false;
num = 0;
}
public void putsize(int y, int x, int val) {
size[y][x] = val;
if(val > 0) {
num++;
}
}
public int getval(int y, int x) {
return size[y][x];
}
}
public static StringBuilder sb = new StringBuilder();
public static java.io.BufferedReader br = new java.io.BufferedReader(new java.io.InputStreamReader(System.in));
static int notebook[][];
static int n;
static int m;
static int k;
static int ans;
static sticker stickers[];
public static void main(String[] args) throws IOException {
String s = br.readLine().trim();
String[] spl = s.split(" ");
n=Integer.parseInt(spl[0]);
m=Integer.parseInt(spl[1]);
k=Integer.parseInt(spl[2]);
notebook = new int[n][m];
stickers = new sticker[k];
//노트북 초기화
for(int i=0; i<n; i++) {
for(int i2=0; i2<m; i2++) {
notebook[i][i2] = 0;
}
}
//스티커 값 넣기
for(int i = 0; i<k; i++) {
s = br.readLine().trim();
spl = s.split(" ");
int sticker_y = Integer.parseInt(spl[0]);
int sticker_x = Integer.parseInt(spl[1]);
stickers[i] = new sticker(sticker_y, sticker_x);
//스티커 배열에 스티커 넣기
for(int i2=0; i2<sticker_y; i2++) {
s = br.readLine().trim();
spl = s.split(" ");
for(int i3=0; i3<sticker_x; i3++) {
stickers[i].putsize(i2, i3, Integer.parseInt(spl[i3]));
}
}
}
solve();
System.out.println(ans);
}
public static void solve() {
ans = 0;
for(int i=0; i<k; i++) {
//마지막 수단 : 돌려서 붙여보기
for(int irt =0; irt<4; irt++) {
//2중for문으로 처음부터 시작점 찾기
for(int iy=0; iy<n; iy++) {
for(int ix=0; ix<m; ix++) {
notebook = attach(iy,ix,i,irt);
if(stickers[i].used == true) {
break;
}
}
if(stickers[i].used == true) {
break;
}
}
if(stickers[i].used == true) {
break;
}
}
if(stickers[i].used == true){
ans = ans + stickers[i].num;
}
}
}
//rotate 0 = 0도, 1 = 90도, 2 = 180도, 3 = 270도
public static int[][] attach(int notebook_y, int notebook_x, int sticker_num, int rotate) {
int rt_x = stickers[sticker_num].x;
int rt_y = stickers[sticker_num].y;
int newnotebook[][] = new int[n][m];
//배열 깊은 복사
for(int i =0; i<n; i++) {
System.arraycopy(notebook[i], 0, newnotebook[i], 0, notebook[i].length);
}
//0 or 180도 회전시
if(rotate == 0 || rotate == 2) {
//붙이려는 지점 + 스티커 길이가 노트북 길이보다 길면 안됨.
if((notebook_x + rt_x > m) || (notebook_y + rt_y > n)) {
return notebook;
}
}
//90 or 270도 회전시
else if(rotate == 1 || rotate == 3) {
if((notebook_x + rt_y > m) || (notebook_y + rt_x > n)) {
return notebook;
}
}
//붙이기
for(int iy=0; iy<stickers[sticker_num].y; iy++) {
for(int ix =0; ix<stickers[sticker_num].x; ix++) {
if(rotate == 0) {
newnotebook[notebook_y+iy][notebook_x+ix]
= notebook[notebook_y+iy][notebook_x+ix] + stickers[sticker_num].getval(iy, ix);
if(newnotebook[notebook_y+iy][notebook_x+ix] > 1) {
return notebook;
}
}
//90 = (x, rt_y-y-1)
if(rotate == 1) {
newnotebook[notebook_y+ix][notebook_x+rt_y-iy-1]
= notebook[notebook_y+ix][notebook_x+rt_y-iy-1] + stickers[sticker_num].getval(iy,ix);
if(newnotebook[notebook_y+ix][notebook_x+rt_y-iy-1] > 1) {
return notebook;
}
}
//180 = (rt_y -y -1 , rt_x - x -1)
if(rotate == 2) {
newnotebook[notebook_y+rt_y-iy-1][notebook_x+rt_x-ix-1]
= notebook[notebook_y+rt_y-iy-1][notebook_x+rt_x-ix-1] + stickers[sticker_num].getval(iy,ix);
if(newnotebook[notebook_y+rt_y-iy-1][notebook_x+rt_x-ix-1] > 1) {
return notebook;
}
}
//270 = (rt_x-x-1,y)
if(rotate == 3) {
newnotebook[notebook_y+rt_x-ix-1][notebook_x+iy]
= notebook[notebook_y+rt_x-ix-1][notebook_x+iy] + stickers[sticker_num].getval(iy,ix);
if(newnotebook[notebook_y+rt_x-ix-1][notebook_x+iy] > 1) {
return notebook;
}
}
}
}
//붙을 수 있으면, 스티커를 사용되었다고 바꿔놓고
stickers[sticker_num].used = true;
return newnotebook;
}
public static String printBoard(){
StringBuilder sb = new StringBuilder();
sb.append("==========================\n");
for(int x=0;x<n;x++){
for(int y = 0; y < m; y++) {
sb.append(notebook[x][y]+" ");
}
sb.append("\n");
}
sb.append("==========================\n");
System.out.println(sb.toString());
return sb.toString();
}
}
결과
아이디
문제 번호
결과
메모리
시간
언어
코드 길이
제출 시간
howtolivelikehuman
18808
맞았습니다!!
383128KB
1400ms
Java
4607B
3달 전
복기
어마어마한 메모리와 시간값을 잡아먹었다. 메모리는 필히 attach 함수에서 매번 깊은 복사로 새 2차원 배열을 생성해서 그럴 것이라고 본다. 하지만 만약 깊은 복사를 하지 않고, 기존의 배열을 매번 초기화 하는 형식으로 사용했다면, 시간이 모자랄 것 같기도 하다. 추가적으로 attach함수에서 2중for문을 돌기 전에 코드가 길어지거나, 새로 함수를 선언하더라도 rotate로 먼저 판별했으면 시간이 더 단축되었을 것 같다.
//붙이기, 떼기만 하는 함수
public static int[][] attach_st(int notebook_y, int notebook_x, int sticker_num, int rotate, int val) {
if(rotate == 0){
for(int iy=0; iy<stickers[sticker_num].y; iy++) {
for(int ix =0; ix<stickers[sticker_num].x; ix++) {
notebook[notebook_y+iy][notebook_x+ix] //val 이 1이면 붙이기, -1이면 떼기
= notebook[notebook_y+iy][notebook_x+ix] + val*stickers[sticker_num].getval(iy, ix);
}
}
}
if(rotate == 1){
.
.
.
}
return notebook;
}
//여기에 겹치는 부분이 있는지 체크만 하는 함수 따로.
이게 뭔가 좋아보이는 이유가, 어차피 스티커는 10*10이라 붙이다 마는거랑 다 붙이고 넘어가는거랑 별 차이가 없기 때문이다. 차라리 붙일 때 마다 조건을 한번씩 더 검사하는게 비효율적 인 것 같다. 클래스를 선언함에 있어서, 원래 속성은 private으로 직접 접근 못하게 하고, getter,setter를 사용하여 조절해야 하는데 귀찮아서 안했다. 그나마 나은 점은 이번에는 쓰여야할 변수가 많아서 이름을 잘 정해준 것 같았다. 사실 문제점은 더 많아보이나, 이런 복잡한 문제는 머리가 아프므로 그만 알아보도록 하겠다.
Comment