문제

https://www.acmicpc.net/problem/1094

설명

이문제는 이해만 하면 알고리즘을 짜는것 자체는 어렵지 않았는데 문제를 이해하는데만 거의 문제풀이 시간의 90 퍼센트가 소요했다. 문제를 제대로 이해해 보자면 다음과 같다. 예를들어 내가 자른 막대기를 가지고 이어 붙혀 23CM 의 막대를 만들려고 한다고 치자. 먼저 처음가지고 있는 막대의 길이는 64CM 이고 이것을 반으로 가르면 두개의 32CM 막대가 나온다. 이중 하나의 막대 32CM 와 우리가 원하는 막대의 길이 23CM 랑 비교했을떄 32CM 가 더 길기때문에 자른막대중 하나를 버리고 다시 위 과정을 우리가 반으로 가른 막대중 하나의 길이가 우리가 목표하는 막대의 길이보다 짧아질때까지 반복한다. 이 케이스의 경우에는 16CM 에서 이 반복을 중단하게 될것이다. 그러면 16CM 막대 2 개가 남게 되는데 이중 하나의 막대는 계속 쪼개면 16, 8 , 4 , 2, 1 … 로 쪼개지게 된다. 여기서 이 막대들을 이어서 23CM 를 만드려면 16CM, 4CM, 2CM, 1CM 의 막대가 필요하다. 따라서 최종적으로 4 개의 막대가 존재해야 우리가 원하는 길이를 만들 수 있다는 결론에 이르게 되어 23 을 넣었을떄 4 가 나오도록 하는 소스를 짜면 정답이된다. 그런데 첫번째 과정, 16CM 까지 막대를 반으로 가르는 부분까지는 어렵지 않지만 그 이후부터는 조합을 어떻게 해야 우리가 목표하는 길이를 맞출 수 있는지 고민해야했다. 처음에는 경우의 수를 모두 for문, 즉 반복문을 이용해 해결해 보려고 했지만 그건 너무 하드코딩, 즉 비효율적으로 판단하여 다른 방법을 모색하던 도중 목표하는 길이 값에서 우리가 자른 막대의 길이를 차례차례 빼면 최종적으로 몇개의 막대가 필요한지 알 수 있다는 것을 깨달았다.예를들어 우리가 23CM 의 길이를 만드는데 조합할 수 있는 막대는 위 예시에서 볼 수 있듯이 16, 8, 4, 2, 1CM(1CM 막대는 두개)가 되는데 위에서 말한 방법을 적용하면 23CM 에서 16CM 막대의 길이를 빼면 7CM 가 되고 8CM 는 7CM 보다 크므로 넘기고 나머지 차례대로 4, 2, 1CM 길이의 막대를 뺴면 최종적으로 23CM 길이의 막대를 만들 수 있고 총 4 개의 막대가 필요하다는 것을 알 수 있다.

코드

#include <stdio.h>

int main() {
    int goal_len,start_len = 64,pole_ea=1; // 목표길이 / 시작길이 = 64 / 이어붙힌 막대 갯수
    scanf("%d",&goal_len);
    while(start_len > goal_len) //반개중 하나가 탈락하지 않을때까지 반복
        start_len /= 2;
    goal_len -= start_len; //더이상 한개가 탈락될일이 없으므로 앞으로 잘려지는 막대기를 이어붙이기 위해 제일 큰 길이의 막대의 길이를 뺀다.
    while(goal_len != 0)    //나머지 막대를 무한정 잘라 길이를 빼서 최종적으로 이어붙힌 길이와 목표길이가 같아질때까지 반복한다.
    {
        start_len /= 2;
        if(goal_len >= start_len)
        {
            goal_len -= start_len;
            pole_ea++;
        }
    }
    printf("%d\n",pole_ea);
    return 0;
}