백준 / 수학 / 막대기 (boj1094, c11)

문제

---

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

1094번: 막대기

 

입출력

---

 

해설

---

이문제는 단순하게 구현하면 된다.

 

하나의 토탈 값을 갖고 있고 모든 값을 저장할 배열하나 갖고 있는다.

 

1. 가장 짧은 것을 절반으로 자른다.

2. 자른 것중 하나를 제외하고 갖고 있는 모든 막대들 더한다.

3. 다 더한 것이 x보다 크거나 같은지 판별하고 맞으면 절반 하나를 버린다. 아니면 둘 다 다시 저장한다.

 

이 순서대로 구현하면 된다.

 

정답코드

---

c언어

#include <stdio.h>
#include <stdlib.h>
/*
 https://www.acmicpc.net/problem/1094
 1094번 막대기
 64
 64 > 23
 16,4,2,1
*/

typedef long long ll;

typedef struct node{//해당하는 값을 arr로 갖는다.
    int v;
}node;

typedef struct vector{//인덱스 접근 가능해야 하며, size 존재, back, pop_back,
    node* arr;//값을 저장하는 곳
    ll size;//크기
    ll capacity;//전체 크기
}vector;

void init(vector *q){
    q->arr=(node *)malloc(sizeof(node)*(64));
    q->size=0;
    q->capacity=64;//초기 크기 64개
}

void push_back(vector *q,int v){//v가 추가되기.
    if(q->size+1<=q->capacity){//
        q->arr[q->size].v=v;
    }else{
        ll new_size= q->capacity*2;
        q->arr = (node*)realloc(q->arr,sizeof(node)*new_size);
        q->arr[q->size].v=v;
        q->capacity=new_size;
    }
    q->size++;//크기 증가
}

void pop_back(vector *q){
    if(q->size){//없을 때는 불러내면 안됨.
        q->size--;//값 줄이기
    }else{
        printf("size가 0이므로 더이상 못 뺌\n");
    }
}

node* back(vector *q){
    node* ret = &q->arr[q->size-1];
    return ret;//값 넘겨주기
}
ll hap=64;//처음에는 64
int x;
main(){scanf("%d",&x);
    vector *arr=(vector *)malloc(sizeof(vector));init(arr);
    push_back(arr,64);//처음에는 64 하나
    while(hap>x){
        node* temp = back(arr);pop_back(arr);
        int half=temp->v/2;
        ll temp_half=0;
        for(int i=0;i<arr->size;i++){
            temp_half+=arr->arr[i].v;
        }
        if(temp_half+half>=x){
            push_back(arr,half);
            hap=temp_half+half;
        }else{
            push_back(arr,half);
            push_back(arr,half);
            hap=temp_half+half*2;
        }
    }
    printf("%d",arr->size);
}