BOJ 18808. 스티커 붙이기

18808번: 스티커 붙이기 (acmicpc.net)

18808번: 스티커 붙이기

 

문제를 푸는 방식은 문제에서 다 알려주기에 그대로 풀면 되지만, 구현하는 과정이 매우 어려웠던 문제다.

 

풀이과정

1. 스티커의 갯수만큼 모든 지점에서 다음 스티커가 들어갈 수 있는지를 판단하는 함수 isAvail()을 실행한다.

2. 만약 한 방향에서 전부 실패하면 그 다음 방향으로 시도해본다.

3. 모든 방향에서 실패하면 다음 스티커로 넘어간다.

 

시간복잡도

스티커 100개, 노트북 뒷면 너비 최대 40*40, 스티커 크기 최대 10*10, 방향 4

4 * 40 * 40 * 10 * 10 * 100 = 64000000번

python은 1초에 약 2천만번의 연산이 가능하므로 약 3초 정도에 해결 가능하다.

python은 C++대비 기준 시간이 보통 3배로 주어지므로 6초 안에 통과 가능하면 된다.

 

여기서 포인트는 90도 회전인데, 배열을 90도 회전하게 되면 다음처럼 배열의 위치가 바뀌게 된다.

배열을 90도 회전한다고 해서 새 배열을 만들면 시간복잡도와 공간복잡도 모두 손해를 보게 되니

기존 배열은 그대로 오름차순으로 참조하되, 스티커의 위치만 위의 배열대로 참조하면 된다.

 

만약 로직을 좀 더 짧게 짜면 다음처럼 된다.

근데 이러면 시간에서 손해봄

왜와이? 코드 반복을 줄이기 위해서 p 배열을 만드는 것을 반복하기 때문. 따라서 기존 시간의 2배가 걸린다.