[알고리즘 수학] 팬 케이크 만들기

팬 케이크를 한번에 두개만 구울 수 있는 팬으로 1이상 n개의 팬 케이크를 만들어야 한다.

모든 팬 케이크는 양쪽을 모두 구워야 하며 한쪽  면을 굽는데 1분이 걸리는데 한장을 굽든 2장을 굽든 시간은 똑같다.

최단 시간에 팬 케이크를 모두 굽는 알고리즘을 설계해 보자.

 

문제풀이)

n=1 일때는 무조건 2분이 걸린다.

n=2 일때도 역시 2분이 걸린다.

n=3 일때는 1,2 를 앞면 구운 다음 1의 뒷면과 3의 앞면을 굽는다. 그 다음 2의 뒷면과 3의 뒷면을 굽는다. 따라서 3분이 걸린다.

n=4 일때도 4분이 걸린다.

n=5 일때 역시 n=2를 먼저 2분에 처리하고 나머지 3개를 같은 방법으로 3분에 굽기 때문에 결국은 n 분이 걸린다.

결국은 n이 1보다 큰 경우에는 모두 n분에 구울 수 있다.

 

c언어로 문제를 풀어 보면 다음과 같다.

int main(){
    int n;
    scanf("%d",&n);
    printf("%d",n>1?n:2);
}