백준 / 정수론 / 가로수 (boj2485, c11)

문제

---

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

2485번: 가로수

 

입출력

---

 

해설

---

내가 새로 심어야 하는 곳은 각 가로수 지점 사이이다.

 

그럼 여기서 문제는 각 가로수 지점 사이에 최소로 지어야 한다면 어떻게 라는 생각이 들 것이다.

 

그러면 최소로 지을 거면 어떻게 해야 될까?

 

다음을 한 번 보자.

 

예를 들어 가로수가

1,3,7,13

예제 1번 처럼 있다고 해보자.

 

그러면 1~3, 3~7, 7~13  이 3개의 사이점 안에 가로수를 지어야 한다.

 

각 사이가 몇 일까?

2, 4, 6 이다.

 

숫자 잘 보면 2의 간격이면 최소라는 것을 알 수 있다.

 

1 , (), 3, (1)5, 7, (1,1)9,11, 13 이런식으로 나온다. (2의 간격이라면)

 

0, 1 , 2 => 3 정답이다.

 

근데 단순히 최소이면 될까?

 

간격이 4,5라면?

 

모두의 간격이 동일하려면 가로수는 1 간격으로 지어져야 될 것이다. 

 

2,4,6 => 2 (간격)

4,5 => 1 (간격)

 

여기서 추론할 수 있는 것은 간격은 모든 간격의 gcd값이라는 것이다.

 

그래서 gcd한 간격을 구한 뒤에 간격들을 돌면서 gcd한 간격들을 나눠주면서 다 더해주면 된다.

 

정답코드

---

c언어

#include <stdio.h>
#include <stdlib.h>
/*
 https://www.acmicpc.net/problem/2485
 2485번 가로수
 x,x1,x2
 4,6의 간격이 있을 때
 2,6,12,18
 4,5 최대 공약수 1
 나오는 간격들의 최대 공약수로 맞히면 된다.
 vector구현하기.
 0,1,2번 인덱스
 a,b,c
*/
typedef long long ll;

typedef struct node{
    int v;
}node;

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

ll gcd(ll a,ll b){
    ll tmp,n;
    if(a<b){
        tmp = a;
        a=b,b=tmp;
    }
    while(b){
        n=a%b;
        a=b,b=n;
    }
    return a;
}

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){//없을 때는 불러내면 안됨.
        free(&q->arr[q->size]);//마지막 값 빼야 됨.
        q->size--;//값 줄이기
    }
}

int n;
ll cnt;
vector* b;
main(){scanf("%d",&n);
    vector *a=(vector *)malloc(sizeof(vector));
    b=(vector *)malloc(sizeof(vector));
    init(a);init(b);
    for(int i=0,t;i<n;i++){
        scanf("%d",&t);
        push_back(b,t);
    }
    int value = b->arr[1].v-b->arr[0].v;
    for(int i=1;i<n;i++){//최대 공약수 알아내기
        int n1 =b->arr[i].v-b->arr[i-1].v;
        push_back(a,n1);
        value=gcd(value,n1);
    }
    for(int i=0;i<a->size;i++){
        cnt+=a->arr[i].v/value-1;
    }
    printf("%lld",cnt);
}