C언어 나무심기

문제

넓이가 가로 100m, 세로 100m인 땅 위에 다음과 같은 모양의 정원을 만들고자 한다. 직사각형과 정사각형의 네변에 일정한 간격으로 나무를 심되, 나무 사는데 드는 비용을 최소한으로 하고자 한다. 몇 m 간격(interval)로 나무를 심어야 하며, 나무는 모두 몇 그루(tree)를 사야 하는가?

<전제조건>

-정사각형의 한 변의 길이 side는 2m 이상이다.

-직사각형의 가로 width, 세로 length 는 30m 이상의 자연수를 입력 받는다.

-사각형의 네 모서리에는 반드시 나무를 심어야 한다.

-사각형이 교차하는 부분은 그림과 같이 4그루의 나무로 정사각형을 이루어야 한다.

-interval은 1m이상 10 미만이어야 하며 나무의 두께는 생각하지 않는다.

-그 외의 지정하지 않은 조건은 문제의 뜻에 맞도록 설계하여 구현한다.

-특히 프로그램의 기능 검증 및 오류 확인을 위한 테스트케이스(Test Case)를 다양하게 설계하고 코드를 구현한 후 테스트해 보라

요구분석

1.입력받는 범위는 가로길이와 세로길이모두 30이상 98이하의 수를 입력받는다.

2.정사각형의 한 변의 길이는 2m 이상50m 미만이다.

3.사각형의 네 모서리에는 반드시 나무를 심어야 한다.

4.사각형이 교차하는 부분은 4그루의 나무로 정사각형을 이루어야 한다.

5.간격은 1~10m 미만이어야 하고, 나무두께는 생각하지 않는다.

6.몇m 간격으로 나무를 심어야하고, 나무는 모두 몇 그루 필요한지 나타낸다.

7.가로+2*(정사각형 한변의 길이-간격)<100

8.세로+2*(정사각형 한변의 길이-간격)<100

 

해결방법

세 정수의 공약수를 이용하여 심어야할 최소의 나무수를 구한다.

배경지식

1.공약수 구하는 공식

2.정사각형은 직사각형에 속한다.

3.사각형 내의 나무의 수 = ((가로길이+세로길이)/간격)*2

 

알고리즘

사용자로부터 가로, 세로, 정사각형 길이를 입력받는다.

while문을통해 가로,세로는 30미만,98초과일 경우, 정사각형의길이는 2미만 50이상일 경우잘못된 입력이라는 문구화 함께 올바른 수를 입력받을 때 까지 반복하여 값을 입력받는다. /*가로,세로의 길이는 최소30, 최대 98까지 가능하고, 정사각형의 길이는 최소 2, 최대49까지 입력 가능하다. */

값에 이상이 없을 경우 break를 통해 while문을 벗어난다.

반복문을 통해 I는 9부터 1씩 감소되며 조건문을통해 세 정수의 공약수일 경우 interval에 값을 넣어 가로 총길이가 100이하일경우와 세로 총길이가 100이하일 경우 break문을 통해 빠져나오도록 만든다.

정사각형의 길이와 간격의 길이가 똑같으면 그다음 공약수를 구한다.

I값이 1이될때까지 계속 반복되어 조건에 성립 하지 못하면 interval은 자동으로 1이 설정된다.

조건문을 통해 w1(가로+2*(정사각형길이-interval))이나 h1(세로+2*(정사각형 길이 - interval))을 초과하면 goto문을 통하여 알고리즘 1로 이동한다.

나무 개수는 직사각형 (가로*2+세로*2)/interval+정사각형한변/interval*4*4- 8(정사각형과 직사각형이 겹치는 수)의 식을통해 구한다.

출력한다.

 

소스코드

#include <stdio.h>

#include <stdlib.h> 

void main()

{

int w,w1,h,h1,interval=0,tree=0,quad,i;

dasi:

printf("30이상,98이하의 가로,세로와 2이상의 정사각형길이를 입력하시오 : ");

scanf("%d %d %d",&w,&h,&quad);

while(1){

if(w<30 || h<30 || w>98 || h>98 || quad<2 || quad>=50 ){

printf("잘못된 입력입니다.\n");

printf("30이상,98이하의 가로,세로와 2이상의 정사각형길이를 입력하시오 : ");

scanf("%d %d %d",&w,&h,&quad);

}

else 

break;

}

for (i=9;i>=1;i--){

if (w%i==0 && h%i==0 && quad%i==0){

interval = i; 

w1 = w +  2 * (quad-interval);  //가로 총 길이 = 직사각형 가로+ (정사각형길이-간격)*2

h1 = h +  2 * (quad-interval);  //세로 총 길이 = 직사각형 세로+ (정사각형길이-간격)*2

if (w1 > 100 || h1 > 100)  //가로 세로 길이가 100을 넘으면 계속 반복

continue; 

else if(quad/interval==1) //최대공약수가 정사각형 값일경우 계속 반복

continue;

else

break;

}

}

if(w1 > 100 || h1 > 100){

printf("계산결과 길이가 100을 초과합니다. ERROR!\n");

goto dasi;

}

tree = (2*(w+h))/interval+quad/interval*16-8;

printf("나무 간격 : %dm \n",interval);

printf("필요한 나무 수 : %d개\n",tree);

}

실행결과

30 30 6의 최대 공약수는 6인데 정사각형의 한변의길이와 interval 값이 같으면 계속 진행하게 되어 그다음 공약수로 다시한번 공식을 확인하게 되어 간격이 3m로 나오게 되었다.

조건에 성립하게 입력을 받았더라도 계산결과값이 100을초과하면 goto문을통해 다시 값을 입력받는 위치로 돌아가는 모습

60 60 30의 공약수는 30 15 6 5 3 2 1 이 있는데, 조건에 성립하는 약수는 6 5 3 2 1이고, 각각의 약수로 길이를 지정하게 되면 한변의 길이가 100을 초과하게 된다.

ex) 60+24*2 > 100 따라서 ERROR!

향후과제

Runtime을 줄일 수 있는 또 다른 방법이 있는지 알아보아야 할 것이다.

 

고찰

이번 과제를 통해 문제의 조건을 모두 만족시킨다는 것이 매우 힘들다는 것을 알 수 있었고, 다양한 결과값 케이스들을 통해 어떤 부분이 문제인지 알아가는 좋은 과제였던 것 같다.

분명 모든 조건이 만족되었겠지? 했는데 아직 충족되지 않은 조건들이 있고, 결과값이 예상한 값대로 나오지 않아 당황하기도 하였고, goto문 같은 경우는 이론으로만 접했었는데 처음 사용해보기도 하여 신기하였다.

좋은 과제일수록 매우 힘들었고 고통스러웠지만, 결국 조건을 모두 충족시킬 수 있어서 매우 큰 성취감을 느낄 수 있었다.