백준 18808 스티커 붙이기

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

18808번: 스티커 붙이기

삼성 역량테스트에서 나올법한 시뮬레이션 문제 

 

최악의 경우 계산 수가 100(스티커 개수) * 4 (회전수) *50* 50(지도 가로세로) * 10 * 10(스티커 가로세로) 해서 1억쯤 되는데 시간초과가 날 줄알았는데 아슬아슬하게 통과하는듯하다.

Gaaaaaaaarden 문제 처럼 삼성 역테 준비한다면 시간 재놓고 1시간 안에 풀어야하는 문제 

 

※ 풀이방법

 

1) 스티커 회전시키는 rotate 함수

2) 회전시킨 스티커를 판에 놓을수 있는가를 체크하는 possible 함수 

 

이 2개만 만들면 아주 간단하게 시뮬레이션 프로그램을 짤 수 있다.

알고리즘 능력이 필요하기보다는 설계능력이 매우 중요한 문제였다.

 

 

package 백준;

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

public class 스티커붙이기 {
	static class MyScanner {
		BufferedReader bf;
		StringTokenizer st;

		MyScanner() {

			bf = new BufferedReader(new InputStreamReader(System.in));

		}

		String next() {

			while (st == null || !st.hasMoreTokens()) {
				try {
					st = new StringTokenizer(bf.readLine());
				} catch (Exception e) {
					e.printStackTrace();
				}

			}
			return st.nextToken();

		}

		int nextInt() {
			return Integer.parseInt(next());

		}

	}

	static class Sticker {
		int r;
		int c;

		int map[][];

		Sticker(int r, int c, int map[][]) {
			this.r = r;
			this.c = c;

			this.map = new int[r][c];
			for (int i = 0; i < r; i++) {
				for (int j = 0; j < c; j++) {
					this.map[i][j] = map[i][j];
				}
			}
		}

	}

	static int N, M, K;
	static int[][] map;
	static Sticker stickers[];
	static int answer = 0;

	private static boolean possible(Sticker s, int x, int y, int map[][]) {
		if (x + s.r > N || y + s.c > M)  return false;
		for (int i = 0; i < s.r; i++) {
			for (int j = 0; j < s.c; j++) {
				if (s.map[i][j] == 1 && map[x + i][y + j] == 1) return false;

			}
		}

		return true;
	}
	static void printMap() {
		for(int i =0 ;i <N;i++) {
			for(int j= 0 ;j<M;j++) {
				System.out.print(map[i][j]+ " " );
			}
			System.out.println();
		}
		System.out.println();
	}
	public static void main(String[] args) {
		MyScanner sc = new MyScanner();

		N = sc.nextInt();
		M = sc.nextInt();

		K = sc.nextInt();
		map = new int[N][M];
		stickers = new Sticker[K];
		for (int k = 0; k < K; k++) {
			int r = sc.nextInt();
			int c = sc.nextInt();
			int[][] temp = new int[r][c];
			for (int i = 0; i < r; i++) {
				for (int j = 0; j < c; j++) {
					temp[i][j] = sc.nextInt();
				}
			}
			stickers[k] = new Sticker(r, c, temp);

		}

		fr:for (int k = 0; k < K; k++) {
			Sticker s = stickers[k];
			for (int l = 0; l < 4; l++) {
				if (l != 0)
					s = rotate(s);
				for (int i = 0; i < N; i++) {
					for (int j = 0; j < M; j++) {
						if (!possible(s, i, j, map))
							continue;
						else {
							for (int ii = 0; ii < s.r; ii++) {
								for (int jj = 0; jj < s.c; jj++) {
									if(s.map[ii][jj]==1)
									map[i + ii][j + jj] = s.map[ii][jj];
								}
							}
							continue fr;
						}
					}
				}
			}
			
		}

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (map[i][j] == 1)
					answer++;
			}
		}

		System.out.println(answer);
	}

	private static void printSticker(Sticker s) {
		System.out.println("printing Sticker");
		for(int i =0 ;i<s.r;i++) {
			for(int j =0 ;j<s.c;j++) {
				System.out.print(s.map[i][j] + " ");
			}
			System.out.println();
		}
		System.out.println();
		
	}
	private static Sticker rotate(Sticker s) {
		Sticker ret = new Sticker(s.c, s.r, new int[s.c][s.r]);

		for (int i = 0; i < s.c; i++) {
			for (int j = 0; j < s.r; j++) {
				ret.map[i][j] = s.map[s.r - j - 1][i];
			}
		}

		return ret;
	}

}