[DFS] 저울 추 ( p. 197 )

오른쪽에 모든 추를 놓아본다.

마지막 추에 대해 무게가 안 맞으면 해당 추를 왼쪽에 놓아본다.

 

반복문으로 중심이 되는 추가 있다. 중심이 되는 추에 대해 위의 과정을 반복하는 것이다.

---

ex)

n=10일 때, 추 ={ 1, 3, 9 }

 

중심 추 1일 때(반복문에서 i=0)

(10) / 1, 3, 9

9 (10) / 1, 3

3, 9, (10) / 1

1,3, 9, (10) /

 

중심 추 3일 때(반복문에서 i=1)

(10) / 3, 1, 9

9 (10) / 3, 1

1, 9, (10) / 3

3, 1, 9, (10) / 

 

중심 추 9일 때(반복문에서 i=2)

(10) / 9, 1 ===============> 끝

3

 

3 (10) / 9, 1

1, 3, (10) / 9

 9, 3, 1, (10) / 

 

1. 어떤 작업을 할 것인지 재귀로 설정 2. base case, return하기 위한 조건 2개만 있으면 전체 탐색은 끝 재귀를 모두 생각할 필요 없다. 첫번째 단계에서 무슨 작업을 해야하는지를 생각하면 된다.