var i_able

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

소요 시간: 약 52분

체감 난도: ★★☆☆☆

사용 언어: C

문제

입/출력 및 예시

풀이

#include <stdio.h>

int num = 1;                // 현재 막대기의 개수
const int MAX = 64;         // 처음 막대기의 길이
int cur_smallest = MAX;     // 현재 가장 짧은 막대기의 길이

// 막대기 총 개수 반환
int re_cut(int answer, int min) {       // 찾는 막대기의 길이와 현재 가장 짧은 막대기의 길이 입력
    if (answer == MAX) {return num;}
    
    num++;          // 막대기를 자름
    min /= 2;
    
    if (min == answer) {    // 내가 찾는 막대기의 길이와 현재 가장 짧은 막대기의 길이가 같으면
        num--;              // 직전에 막대기를 잘랐으니 같은 길이의 막대기가 하나 더 있음 -> 버리기
        return num;         // 막대기 개수 반환
    }
    else if (min > answer)  // 내가 찾는 막대기의 길이보다 현재 가장 짧은 막대기의 길이가 더 길면
    {
        num--;              // 직전에 자른 막대기 버리기
        return re_cut(answer, min);     // 찾는 답과 반으로 짧아진 가장 짧은 막대기의 길이 입력
    }
    else {                  // 내가 찾는 막대기의 길이보다 현재 가장 짧은 막대기의 길이가 짧으면
        return re_cut(answer-min, min); // 내가 찾는 길이에서 현재 가장 짧은 막대기 길이 뺀 길이 입력
    }
    
}

int main(void)
{
    int answer;
    
    scanf("%d", &answer);
    
    int number = re_cut(answer, cur_smallest);
    
    printf("%d\n", number);
    
    return 0;
}

개선사항

재귀함수를 만들어서 써보는 건 처음이었는데, 역시나 계획 없이 무작정 짰다! 재귀 함수 쓸 때 아이디어를 먼저 떠올리고, 증명으로 검토한 후에 코드를 짜는 것이 더 안전할 것 같다. 사실 시도는 했으나 어떤 걸 증명의 대상으로 둬야 할 지 어려움이 있었다. 재귀 함수를 더 써보면서 무엇을 증명해야 할지 염두에 두는 것이 좋겠다.