[백준 BOJ] 12005번 Diamond Collector (Bronze) (C++/cpp)

문제 설명

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

12005번: Diamond Collector (Bronze)

 

접근 방법 - 브루트포스 알고리즘의 기초 문제

백준의 12005번 문제는 브루트포스 알고리즘을 이용하여 간단하게 해결할 수 있는 문제이다.

해당 문제는, 다이아몬드를 진열할 때 각 크기의 차이가 k 이하여야 한다면 진열할 수 있는 다이아몬드의 최대 개수를 출력해야 하는 문제이다.

각 다이아몬드들끼리의 크기 차이가 특정값 이하여야 하기 때문에, 필자는 정렬도 추가적으로 응용하였다.

그렇게 정렬된 값들에 있어 특정 영역을 탐색하며, 양 끝 크기의 차이를 기준점으로 두어 답을 구하도록 해보았다.

자세한 설명은 아래에 있으니, 혹여나 해당 문제를 해결하는 데에 어려움을 겪고 있다면, 아래의 설명과 코드를 참고해보길 바란다. 

필자는 아래의 순서대로 코드를 작성하여 문제를 해결하였다.

 

코드의 실행 순서

1) 다이아몬드의 크기들을 입력받을 배열(dia)을 전역 변수로 미리 선언해 둔다.

 

2) 다이아몬드의 개수(n)와 지켜야 하는 각 크기의 차이(k)를 입력받는다.

 

3) n의 크기만큼 반복문을 실행하여, dia의 값들을 하나씩 입력받는다.

 

4) sort()를 통해, dia의 값들을 오름차순으로 정렬한다.

 

5) 진열할 수 있는 다이아몬드의 최대 개수를 저장할 변수 max를 0으로 초기화하며 선언한다.

 

6) 2중 반복문을 통하여, 아래의 연산을 취하도록 한다.

- 2중 반복문으로 인하여 지정된 특정 범위가 있을 것이다.

이에 대해, 양 끝에 위치한 다이아몬드의 크기 차이가 k 이하이며 해당 범위의 크기가 max를 넘어선다면, max의 값을 해당 값으로 갱신하도록 한다.

 

7) 연산이 모두 완료되었다면, 최종적으로 저장된 max의 값을 출력한 뒤 실행 종료한다.

반응형

 

성공한 코드

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#include <iostream>
#include <algorithm>
#define endl '\n'
using namespace std;

//백준 12005번 코드
int dia[1001];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);	cout.tie(NULL);

	int n, k;
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		cin >> dia[i];
	}
	sort(dia, dia + n);

	int max = 0;
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			if (dia[j] - dia[i] <= k && j - i + 1 > max) {
				max = j - i + 1;
			}
		}
	}
	cout << max << endl;
}

 

제출 결과

(2022.12.09 백준 12005번 문제 제출 결과)