[C] 백준 - 2485번: 가로수

5월 3일(수) - 약수, 배수와 소수2 (2485번)

2485번: 가로수

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

최초 생각 정리

- N개의 가로수의 위치는 tree 배열에 입력받고, 이를 토대로

  N-1개의 가로수 사이의 거리는 distance 배열에 distance[ i ] = tree[ i+1 ] - tree [ i ]로 입력한다

- 이제 distance배열에 들어있는 N-1개의 값들을 가지고, 해당 값들의 최대공약수를 구한다

  이때 구한 최대공약수는 변수 gcd_of_distance에서 갱신하면서 저장해준다

- 가로수의 가장 처음 위치인 tree[1]에다가 gcd_of_distance값을 계속해서 더해가며

  tree배열에 이미 존재하는 값과 같은지 / 다른지를 조건으로 if문을 나누며 count++을 해준다

- 최종적으로 count를 출력

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

문제점

// 수정 전
	int tmp = tree[1];
	int count = 0;
	for (int i = 1; i <= N; i++)
	{
		if (tmp != tree[i])
		{
			tmp = tmp + gcd_of_distance;
			count++;
		}
		else
		{
			continue;
		}
	}
    
// 수정 후
	int count = 0;
	for (int i = 1; i < N; i++)
	{
		count = count + (distance[i] / gcd_of_distance) - 1;
	}

1. 가로수의 가장 처음 위치인 tree[1]에다가 gcd_of_distance값을 계속해서 더해가며

  tree배열의 값과 같은지 / 다른지를 조건으로 if문을 나누며 count++을 해준다

-> gcd_of_distance 값을 계속 더해주는 것은 너무 비효율적인 방법인듯 + 코드가 너무 복잡해짐

-> 변수 count에다가 distance[ i ] 값을 gcd_of_distance로 나눈값을 계속 더해주며 누적합을 카운트하도록 변경

-> 이때 매번 -1을 해주어야함

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)

#include <stdio.h>
int tree[100000];
int distance[100000];

// 최대공약수(Greatest Common Divisor) 구하기
int GCD(int a, int b)
{
	if (b == 0)
	{
		return a;
	}
	else
	{
		return GCD(b, a % b);
	}
}

int main(void)
{
	int N;
	scanf("%d", &N);

	for (int i = 1; i <= N; i++)
	{
		scanf("%d", &tree[i]);
	}
	for (int i = 1; i < N; i++)
	{
		distance[i] = tree[i + 1] - tree[i];
	}
	
	int gcd_of_distance = tree[2] - tree[1];
	for (int i = 1; i < N; i++)
	{
		gcd_of_distance = GCD(gcd_of_distance, distance[i]);
	}

	int count = 0;
	for (int i = 1; i < N; i++)
	{
		count = count + (distance[i] / gcd_of_distance) - 1;
	}

	printf("%d", count);
	return 0;
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ