문제 해결 전략
-
5개의 크기의 색종이가 5개씩 있다.
-
25개를 가지고 1인 적힌 구간을 덮어나가는 문제이다.
-> 시간복잡도를 구하기 굉장히 어렵고, 뭔가 많을 듯하다.
왜냐하면 사각형을 만들고, 다른 사이즈 선택해서 또 재귀로 이루어지는 구조를 생각할 수 있다.
아이디어.
- 일단은 큰색종이를 최대한 활용하면 최소 카운팅을 구할 수 있다.
는 것을 생각할 수 있다.
-
조건 처리 없이 생각해본다면, pos는 총 100개이고,
25개를 가지고 조합을 해야하므로,
100! / 75! * 25!
-> 100 ~ 76 까지 곱하고, 25! 나눠야 하므로, 굉장히
높은 시간복잡도이다. -
생각해볼 것들.
-> 어쨋든 브루트포스인데 , 가지치기를 통해서 시간복잡도를 줄여보자.
백트래킹
- 기저사례
: 우리는 최소값을 구하는 것이므로 카운팅 값이 ret보다 크면 진행할 필요 없다.
- 재귀를 어떻게 진행할지 생각해보자.
-> 우리는 x축 기준으로 증가하면서 진행하는 구조로 만들거기 때문에
-> 재귀코드를 작성함.
- 최소값 정하는 부분.
- 우리는 1인 부분에 관해서만 진행하므로, 0을 발견하면 해당 (y,x)를 가지고 진행할 필요가 없다.
순서 중요하다.
- 기저사례는 반드시 맨 위에 위치하고
- 화살표의 2개는 변경해도 되지만,
- 아래의 69번 조건 처리 순서를 위에 올리면 out of bound 발생.
- 마지막으로 백트래킹 코드
결론
- 백트래킹 하기로 했으므로, 코드를 잘게 잘게 잘라야 한다.
1) 기저 사례 필요
2) 재귀 돌릴 코드 필요
3) 백트래킹 할 코드 필요.
🔥🔥🔥