현재 코드가 최소 개수를 제대로 찾지 못하는 이유는, 사다리를 추가하는 개수를 고정하지 않고 한꺼번에 0부터 3개까지 모두 탐색하면서, 처음 찾은 답에 바로 멈춰버리기 때문입니다. 이렇게 되면 탐색 순서에 따라 더 많은 사다리를 추가한 답이 먼저 발견되면 그걸 정답으로 받아버려서, 실제 최소 개수를 찾지 못할 수 있어요.
따라서 문제를 해결하려면, 먼저 사다리를 0개 추가하는 경우부터 완전히 탐색해서 답이 있는지 확인하고, 없으면 1개 추가하는 경우를 완전 탐색하는 식으로 단계별로 시도해야 합니다. 이렇게 하면 최소 개수를 보장할 수 있습니다.
또한, 전역변수로 두고 있는 정답 변수를 적절히 초기화하고, 새로운 답을 찾으면 최소값으로 갱신하는 구조가 되어야 합니다. 그리고 답을 찾았다고 해서 바로 탐색을 종료하기보다는, 최소 개수를 우선 탐색하는 전략을 통해 불필요한 탐색을 줄이고 정확한 답을 찾는 것이 중요합니다.
즉, “몇 개를 추가할 것인지”를 먼저 정해놓고, 그 개수로 가능한 모든 경우를 탐색하는 방식을 구현해야 정확한 최소 개수를 구할 수 있습니다.

mintuchel 1년 전
예제 모두 돌아가는데 아래 반례들에서 걸리네요.
위치 h에 높인 M 행 사다리를 map[H][M] 2차원 bitset을 통해 표현했습니다.
map[h][m]이 1이라는 것은 h 높이에 m-m+1 사다리가 놓여졌다는 것입니다.
각 M행의 종료지점이 M인지 확인해주는 check 함수와 사다리를 조합 + 백트래킹으로 놓는 solve 함수 모두 맞는 것 같은데 왜 이렇게 출력되는지 모르겠네요.
그리고 현재 제 solve 함수는 답을 찾으면 바로 true를 반환해서 더 이상 탐색 안하고 바로 종료되는 구조 아닌가요?
check 함수에서 cnt 즉, 사다리의 개수는 1부터 3까지 진행되니 만약 cnt가 1일때 만족했으면 사다리를 2개 3개까지 놓지 않고 바로 종료되는 구조 아닌가요?
그런데 왜 이런 반례들이 생기는지 모르겠습니다...
고수님들 알려주시면 정말 감사하겠습니다.
3 1 4
4 2
출력 : 3
정답 : 1
4 1 3
3 3
출력 : 3
정답 : 1
4 1 4
2 2
출력 : 3
정답 : 1