티스토리 뷰
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
|
import java.io.*;
import java.util.*;
public class boj_18808 {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static int n, m, k, ans;
static int[][] board;
static int[] startPoint;
static List<int[][]> stickers = new ArrayList<>();
public static void main(String[] args) throws IOException {
input();
solve();
printAns();
}
static void solve() {
// 모든 스티커에 대해서 검사
for (int[][] sticker : stickers) {
// 스타트 가능한 부분 찾기, (0, 0) ~ (maxXSize, maxYSize)
int[] canStartDotMax = findDot(sticker);
// 가능한 부분인지 확인하기 -> 가능하다면 startPoint 에 시작하는 x, y 좌표 담음
boolean possibleToStart = isPossibleToStart(canStartDotMax, sticker);
if (possibleToStart) {
// 스티커 붙이기
attachSticker(sticker); // startPoint[] static 주의
} else {
// 스티커 회전하기 90, 180, 270도
for (int turnCount = 1; turnCount <= 3; turnCount++) {
int[][] turnSticker = rotate(turnCount, sticker);
int[] dot = findDot(turnSticker);
if (isPossibleToStart(dot, turnSticker)) {
attachSticker(turnSticker); // startPoint[] static 주의
break; // 이미 스티커를 붙였다면 다음 스티커로 넘어감
}
}
}
}
}
static int[][] rotate(int turnCount, int[][] sticker) {
// do turn, turnCount 1 - 90, 2 - 180, 3 - 270 도
int row = sticker.length;
int col = sticker[0].length;
int[][] turnSticker;
// 회전시키기
if (turnCount == 1) { // 90
turnSticker = new int[col][row];
for (int i = 0; i < col; i++) {
for (int j = 0; j < row; j++) {
turnSticker[i][j] = sticker[row-1-j][i];
}
}
} else if (turnCount == 2) { // 180
turnSticker = new int[row][col];
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
turnSticker[i][j] = sticker[row-1-i][col-1-j];
}
}
} else { // 270
turnSticker = new int[col][row];
for (int i = 0; i < col; i++) {
for (int j = 0; j < row; j++) {
turnSticker[i][j] = sticker[j][col-1-i];
}
}
}
return turnSticker;
}
static void attachSticker(int[][] sticker) {
int x = startPoint[0];
int y = startPoint[1];
int row = sticker.length;
int col = sticker[0].length;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (sticker[i][j] == 1) {
board[i + x][j + y] = sticker[i][j];
}
}
}
}
static boolean checkPoint(int x, int y, int[][] sticker) {
int row = sticker.length;
int col = sticker[0].length;
boolean flag = true;
all : for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (sticker[i][j] == 0) continue;
if (board[i + x][j + y] == 1) { // 이미 스티커가 붙여져있으면
flag = false;
break all;
}
}
}
return flag;
}
static boolean isPossibleToStart(int[] now, int[][] sticker) {
int maxX = now[0];
int maxY = now[1];
if (maxX < 0 || maxY < 0) return false;
// 0 ~ maxX , 0 ~ maxY
boolean flag = false;
all : for (int startX = 0; startX <= maxX; startX++) {
for (int startY = 0; startY <= maxY; startY++) {
// 시작포인트에서 스티커를 붙일 수 있는가 를 확인
if (checkPoint(startX, startY, sticker)) {
startPoint = new int[] { startX, startY };
flag = true;
break all;
}
}
}
return flag;
}
static int[] findDot(int[][] sticker) {
int xSize = sticker.length;
int ySize = sticker[0].length;
// find startDot
int maxXSize = n - xSize;
int maxYSize = m - ySize;
return new int[] { maxXSize, maxYSize };
}
static void input() throws IOException {
st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
k = Integer.parseInt(st.nextToken());
board = new int[n][m];
for (int i = 0; i < k; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int[][] sticker = new int[a][b];
for (int j = 0; j < a; j++) {
st = new StringTokenizer(br.readLine());
for (int l = 0; l < b; l++) {
sticker[j][l] = Integer.parseInt(st.nextToken());
}
}
stickers.add(sticker);
}
}
static void printAns() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (board[i][j] == 1) ans++;
}
}
System.out.println(ans);
}
}
|
cs |
- 시뮬레이션
- 어려움
- 어제도 고민하고 오늘도 계속 붙잡아서 겨우 성공
- 접근 자체가 생각이 안나는건 아니고 생각한걸 코드로 짜내는 과정이 어려웠음
1. 스티커를 list에 저장
2. 스티커의 제일 끝을 기준으로 스티커를 붙일 수 있는 최대 시작 포인트의 x, y 좌표 저장 canStartDotMax
3. 0~최대X, 0~최대Y 값을 기준으로 붙일 수 있는지 확인 isPossibleToStart
4. 가능 하다면 스티커 붙이기 attachSticker
5. 불가능하다면 90, 180, 270도 순서로 회전 시킨후 위의 과정 반복 rotate
'PS > boj' 카테고리의 다른 글
boj)10973 - 이전 순열 (0) | 2020.11.30 |
---|---|
boj)10972 - 다음 순열 (0) | 2020.11.30 |
boj)15683 - 감시 (0) | 2020.11.25 |
boj)1182 - 부분수열의 합 (0) | 2020.11.23 |
boj)9663 - N-Queen (0) | 2020.11.19 |
링크
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
TAG
- 김영한 JPA
- 이펙티브자바
- GCP
- 킹수빈닷컴
- 프로그래머스 SQL
- HTTP 완벽 가이드
- JPA 연관관계 매핑
- js array
- http
- 이펙티브자바 아이템60
- REST API
- 패스트캠퍼스 컴퓨터공학 완주반
- 백준
- Spring Security
- dreamcoding
- 이펙티브자바 아이템59
- js api
- 모던자바스크립트
- HTTP 완벽가이드
- BOJ
- js promise
- ㅇㄷㅇㅈ
- 백기선 스터디
- JS 딥다이브
- 프로그래머스
- 드림코딩
- 이펙티브자바 스터디
- 가상 면접 사례로 배우는 대규모 시스템 설계 기초
- 김영한 http
- java
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
7 | 8 | 9 | 10 | 11 | 12 | 13 |
14 | 15 | 16 | 17 | 18 | 19 | 20 |
21 | 22 | 23 | 24 | 25 | 26 | 27 |
28 | 29 | 30 |
글 보관함