완전 탐색. [2309, 1182]

[1. 문제 설명]

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

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

---

[2. 풀이 접근]

이번 문제는 재귀를 이용한 전형적인 완전 탐색 문제이다.

여기서는 재귀 구현 방식에 대한 내용을 정리한다.

 

개인적으로 재귀를 이용한 완전 탐색 구현 시 코드는 아래 두가지 패턴이 있다고 생각한다.

1. 반복문 없이 재귀를 여러번 호출
2. 반복문 내부에서 재귀를 호출

단, 두 패턴 사용은 상황에 맞게 적절히 사용해야 한다.

 

먼저은 1182 풀이이다.

여기서는 1번 패턴으로 작성한 코드만 통과한다.

2번 패턴이 틀린 이유는 코드 구조 상 마지막 원소만 선택되지 않은 경우를 체크 할 수 없기 때문이다.

• index == N-1 인 경우에 재귀 호출을 한번 더 해보도록 해봤는데도, 오답이었다.

다음  2309 풀이이다. 두 가지 모두 통과한다.

1182 와 달리 두번째 패턴으로도 통과하는 이유는 N 개중 K 를 선택하기 때문이며,
=> (마지막 원소 미 포함 여부가 크게 중요하지 않아 보임?)

모든 경우를 찾을 필요가 없기 때문이다.

따라서 경우에 따라서는 틀릴 수 도 있기에 왼쪽 코드가 더 정확하다고 볼 수 있다..

 

정리하면 각 구현 패턴을 사용하는 경우를 구분 할 줄 알아야 한다.