2025년, 코딩은 선택이 아닌 필수!

2025년 모든 학교에서 코딩이 시작 됩니다. 먼저 준비하는 사람만이 기술을 선도해 갑니다~

강의자료/알고리즘 수학

[알고리즘 수학] 막대자르기

원당컴1 2023. 4. 14. 11:19

길이가 100인 막대를 잘라 길이가 1인 조각 100개를 만들어야 한다. 여러 조각을 한꺼번에 자를 수 있다고 가정할 때 자르는 최소 횟수는 몇번인가?

막대의 길이가 n일때 최소 횟수만에 자르는 알고리즘을 설명하라.

문제출처) 길벗 - 알고리즘 퍼즐

 

문제풀이)

이 문제는 정보올림피아드 예선 문제에 자주 출제되는 유형으로 다음과 같이 절반씩 잘라 가는 유형으로 생각하면 됩니다.

100 = 50 * 2

50 = 25 * 2

25 = 13 + 12 (여기서 13 크기를 기준으로 생각함)

13 = 7 + 6 (여기서 7 크기를 기준으로 생각함)

7 = 4 + 3 (여기서 4 크기를 기준으로 생각함)

4 = 2*2

2 = 1*1

즉 7번이면 100인 막대를 1 크기로 모두 자를 수 있습니다.

여기서 아이디어는 절반씩 잘라 간다는 것입니다.

즉 2까지는 1회, 4까지는 2회,8까지는 3회,16까지는 4회, 32까지는 5회, 64까지는 6회,128까지는 7회로 가능합니다.

즉 2^k 이 n의 값 이상이라면 k 회수 안에서 자를 수 있습니다.

 

C++

int main(){
    int n,k;
    cin >> n;
    for(k=1; 1<<k < n; k++);
    cout << k;
}
사업자 정보 표시
원당컴퓨터학원 | 기희경 | 인천 서구 당하동 1028-2 장원프라자 502호 | 사업자 등록번호 : 301-96-83080 | TEL : 032-565-5497 | Mail : icon001@naver.com | 통신판매신고번호 : 호 | 사이버몰의 이용약관 바로가기