백준(BOJ) 16951 블록 놀이

문제 : https://www.acmicpc.net/problem/16951

16951번: 블록 놀이

 

풀이 :

해당 배열 인덱스 하나당 기준으로 잡고 k 만큼 차이나는 배열을 만들어보자.

 

예를 들어 2 4 6 9이고 k가 1이라면

 

2 3 4 5

 

3 4 5 6

 

4 5 6 7

 

6 7 8 9 

 

이 4개의 후보들 중 정답이 있게 된다.

 

이때 새로 만든 배열이 1보다 작다면 바로 pass 하자.

 

 

코드 (C ++ )

	#include <iostream>
	#include <vector>
	#include <algorithm>
	using namespace std;
	int n, k;
	const int INF = 987654321;
	int main()
	{
	cin >> n >> k;
	vector<int>a(n);
	for (auto& i : a)
	cin >> i;
	int minAns = INF;
	for (int i = 0; i < n; ++i) {
	vector<int> temp(n);
	temp[i] = a[i];
	int impos = 0;
	for (int j = i - 1; j >= 0; --j) {
	temp[j] = temp[j + 1] - k;
	if (temp[j] <= 0) {
	impos = 1;
	break;
	}
	}
	if (impos) continue;
	for (int j = i + 1; j < n; ++j) {
	temp[j] = temp[j - 1] + k;
	}
	int cnt = 0;
	for (int i = 0; i < n; ++i) {
	if (a[i] != temp[i])
	cnt++;
	}
	minAns = min(cnt, minAns);
	}
	cout << minAns << "\n";
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub