[프로그래머스] 두 동전

물류센터를 갔다와서 너무 피곤한 관계로 예상 풀이만 적어두고 나중에 풀어볼 생각입니다 ㅠ...

일단 최근에 풀었던 짠돌이 호석과 똑같은 풀이라고 생각합니다.

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

21277번: 짠돌이 호석

짠돌이 호석은 입력이 50까지이고, 정사각형이 아닌 직사각형이 주어질 수 있고, 직사각형이므로 어떤 블럭을 기준으로 해야 할지 난감하고, 직사각형이므로 돌렸을 때 모양이 바뀌기도 하므로 지금 보니 오늘 풀어야 했던 자물쇠와 열쇠보다 어려운 문제라고 생각이 들었습니다.

풀이는 마찬가지지만 차이가 몇가지 있다면 직사각형이 아닌 정사각형만 주어지고, 무조건 자물쇠의 크기가 열쇠보다 크므로 짠돌이 호석에서는 최대 크기의 배열을 선언해주었지만 여기서는 (자물쇠의 크기+2*(열쇠의 크기-1(적어도 하나는 겹쳐야 하므로)))의 배열을 선언해주면 될 것이라고 생각했습니다. 이경우 배열 한 변의 최댓값은 (20+38) 58

꼭짓점을 잡고 탐색을 해보면

열쇠의 맨 오른쪽 아래 꼭짓점이 자물쇠 왼쪽 위의 꼭짓점과 겹치는 곳부터 시작해서 열쇠의 맨 왼쪽 위 꼭짓점이 자물쇠 오른쪽 아래 꼭짓점과 만나게 되는.. 열쇠의 맨 왼쪽 위 꼭짓점을 기준으로 다음과 같은 구역만 탐색하면 됩니다.

O 1	O 2	X
O 3	O 4	X
X	X	X

최대 (20+19)^2가지 경우의 수에 대해서 (1600미만) 최대 400칸 탐색 1600*400=640000 돌린 경우까지 곱해줘서 *4해줘도 백만자리 매우 안정적인 통과가 가능할 것 같습니다. 탐색의 일반적인 경우의 수는 맨 왼쪽위(열쇠의 크기-1)+2(열쇠의 한 변 * 자물쇠의 한 변-1)+(자물쇠의 크기)가 될 것 같습니다. (1번영역 + 2*(2번 영역) + 4번 영역) (2번영역과 3번영역의 크기는 무조건 같으므로).. 그리고 중간중간 만약 홈끼리 겹친다는 등의 문제가 발생하면 탈출시켜주고 하면 안정적으로 문제를 풀 수 있을 것 같습니다.