1094)막대기

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

알고리즘을 말로 설명해주고 있어 알고리즘을 짜는 것은 어렵지 않다.

64,32,16,8,4,2,1 중 하나 씩 더해서 64 이하의 수들을 표현할 수 있다.

예를들어 23은 16,4,2,1 을 더해서 얻을 수 있다.

위 수들은 2를 0~6번거듭제곱해서 얻을 수 있다는 점을 이용해

len[7]을 선언하고 len[6]에 1을 할당해주면 초기 상태를 만들 수 있다.

len[6]=1은 2^6이 하나 있다는 뜻이다.

#include<stdio.h>
#define NUM 7
 
int customPow(int n) {
    int result = 1;
 
    for (int i = 1; i <= n;i++) {
        result *= 2;
    }
 
    return result;
}
 
int main() {
    int len[NUM] = {0};
    int minIndex;
    int X;
    int sum = 64;
    int cnt = 0;
 
    len[6] = 1;
    scanf("%d",&X);
 
    while (sum!=X) {
        sum = 0;
 
        for (int i = 0; i < NUM;i++) {
            if (len[i] > 0) {
                minIndex = i;
                break;
            }
        }
 
        if (minIndex>0) {
            len[minIndex]--;
            minIndex--;
            len[minIndex] += 2;
            
        }
        
 
        for (int i = minIndex; i < NUM;i++) {
            
            if (len[i] > 0) {
                sum += customPow(i);
            }
            
        }
 
        if (sum>=X) {
            len[minIndex]--;
        }
        
    }
 
    for (int i = 0; i < NUM;i++) {
        cnt += len[i];
    }
 
    printf("%d\n",cnt);
 
    return 0;
}