C언어 9제] 깊이 우선 탐색(DFS) 이용한 프로그램 구현하기

출처] 반크 독도포스터

 

 

깊이 우선 탐색이란? (참고 : DFS)

 

문제]

길이 8m의 막대를 3명이서 1m단위로 자를려고 할 때 몇 번이면 1m 막대가 될 수 있는지 프로그램을 작성하시오.(단, 하나의 막대는 한 사람만 자를 수 있다.)
8 -> 4, 4 로 자른다 1명
4, 4 -> 2, 2, 2, 2로 자른다 2명
2,2,2 -> 1,1,1,1,1,1로 자른다 3명
2 -> 1,1로 자른다 1명
그러므로 총 4번을 자르면 8m 막대가 1m막대로 만들수 있게 된다.

입력 예시1]
20, 3

출력 예시1]
8


입력 예시1]
100, 5

출력 예시1]
22

 

 

참고풀이]

#include <stdio.h>

//x : 최종 막대기 총수
//y : 막대기를 자를 인원수
//count : 현재 자를 막대기 개수 
int Jarki_DFS(int x, int y,int count)
{
   static int cnt=0;
   if(count>=x) return cnt;
   cnt++;
   if(count<y) return Jarki_DFS(x,y,count*2);
   else return Jarki_DFS(x,y,count+y);
}

int main()
{
   int a,b;

   scanf("%d%d",&a,&b);
   printf("%d\n",Jarki_DFS(a,b,1));

   return 0;
}

 

결과]

 

 

 

대한민국의 아름다운 영토, 독도의 여름