[BOJ] 18808 스티커 붙이기
문제 조건
노트북에 스티커를 붙일 예정이다.
1<=N,M<=40 : 노트북의 세로, 가로
1<=K<=100 : 스티커 개수
K개의 줄에
1<=Ri, Ci<=10 : i번째 스티커의 행, 열 개수
다음 줄부터 스티커 모양 (0:인쇄 안됨, 1:인쇄 됨) 이 주어진다.
예시에 있는 그림인데 예로 들면
1 0 1
1 1 1
1 0 1
이런 식. (무조건 그림이 꽉 들어찬 직사각형 모양으로 주어짐)
1. 스티커는 들어온 순서대로 겹치지 않도록 붙일 수 있는 가장 위(여러개면 가장 왼쪽) 에 붙인다.
2. 스티커를 붙일 수 없으면 90도 시계방향으로 회전 후 재시도한다.
3. 못붙이면 버린다.
모든 스티커를 처리했을 때, 노트북에 스티커가 붙어있는 면적 출력하기.
접근 방식
N,M,R,C,K가 다 작고 붙일 수 있는 경우의 수가 여러개인게 아니기 때문에 (무조건 위 왼쪽, 붙일 수 있으면 붙임) 다 시도해보면 풀린다. 구현을 실수하지 않고 할 수 있냐의 문제...
(// TODO 자세하게 좀 써보기)
구현 해야할 부분을 큼직하게 생각해보자.
1. Input Output
2. 0,0부터 N-R-1, M-C-1까지 붙일 수 있을지 확인 후 스티커 붙이기
3. 스티커 회전
이렇게 3개 정도가 있을 것 같다.
2에서 N-R-1, M-C-1 까지만 확인하는 이유는, 스티커는 무조건 그림이 꽉찬 모양으로 주어지니까, N-R ~ N-1 를 스티커와 대조할 첫 칸으로 정하면 노트북 크기를 넘어가버리므로 확인할 필요가 없다.
조심해야할 건 90도 회전...
0,0 -> 0,r-1 이렇게 바뀌니까, --> (i,j) -> (j,r-1-i) 로 바뀌고, r,c가 서로 바뀌는 것만 기억해두면 된다...
여담
삼성 기출처럼 생긴 문제들은 반드시... 짚고 넘어가야 할게 있는데, 바로 **가로, 세로** 이다.
나만 맨날 헷갈리는건지 모르지만... 무조건 가로 세로때문에 한 번은 꼭! 반드시! 틀리더라... 특히 회전이 들어가면 더...
어릴적의 나는 너무 덤벙대서 (지금도지만) 맨날 가로, 세로 때문에 고생했다.
코드
맨날 예쁘게 짜야지.. 하고 노력하는데 별로 예쁘게 안짜지는 것 같다... 전역변수도 많이 썼다.
코테볼땐 전역변수 쓰는게 맘편하다...