뚝딱뚝딱

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=3&contestProbId=AV139KOaABgCFAYh&categoryId=AV139KOaABgCFAYh&categoryType=CODE&problemTitle=&orderBy=INQUERY_COUNT&selectCodeLang=ALL&select-1=3&pageSize=10&pageIndex=1

✅ 문제 풀이

• 상자의 높이를 입력 받은 벡터에서, 가장 큰 값은 1 줄이고, 가장 작은 값은 1 늘리는 식으로 평탄화할 수 있다.
• 한번 덤프를 수행하고 날 때마다, 최소의 상자 높이와 최대의 상자 높이를 갖는 벡터의 위치가 달라진다.
• 이를 쉽게 찾기 위해서 매 덤프마다 벡터를 오름차순 정렬하고 시작하기로 했다.
• 그렇게 하면 벡터의 0번은 항상 가장 작고, 99번은 항상 가장 크기 때문이다.
• 따라서 정렬 후, 벡터의 99번째와 0번째의 차이가 1 또는 0이라면 더이상 상자를 옮기지 않아도 되기 때문에, break문으로 덤프를 멈추도록 한다. 그렇지 않다면, 평탄화가 이루어 져야 하므로 99번째 상자는 하나 줄이고, 0번째 상자는 하나 높여준다.
• 그럼 다음 덤프에서 다시 오름차순 정렬되고, 위의 과정을 반복하면 된다.
• 덤프를 모두 수행하고 나서는, 최종적으로 한번더 오름차순 정렬해준 뒤, 99번째에서 0번째 값을 뺀 값을 출력하도록 하면 된다.

=> 굉장히 naive한 방법이지만, c++ 기준 시간은 10초까지 인정되므로 pass되는 코드이다.

✏ 코드 전문

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	for (int i = 1; i <= 10; i++) {
		int n;
		cin >> n;
		vector<int> arr(100);
		for (int j = 0; j < 100; j++) {
			cin >> arr[j];
		}
		
		int answer;
		for (int j = 0; j < n; j++) {
			sort(arr.begin(), arr.end());
			if (((arr[99] - arr[0]) == 1) || ((arr[99] - arr[0]) == 0)) {
				break;
			}
			else {
				arr[99]--;
				arr[0]++;
			}
		}
		sort(arr.begin(), arr.end());
		answer = arr[99] - arr[0];
		cout << "#" << i << " " << answer << "\n";
	}
	return 0;
}

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=3&contestProbId=AV134DPqAA8CFAYh&categoryId=AV134DPqAA8CFAYh&categoryType=CODE&problemTitle=&orderBy=INQUERY_COUNT&selectCodeLang=ALL&select-1=3&pageSize=10&pageIndex=1

난이도 D3 ⭐⭐⭐

✅ 문제 풀이

• 처음 두 건물과, 마지막 두 건물은 항상 높이가 0이다.
• 따라서 세번째 건물부터 기준으로하여, 앞에 두 건물과 뒤에 두 건물 보다 큰지 확인한다.
• 앞 뒤로 총 4개의 건물보다 크다면, 기준이 되는 현재 건물의 높이에서 4개 건물 중 가장 큰 건물의 높이를 뺀 값이 뷰를 확보할 수 있는 세대 수가 된다.
• 이를 모든 건물에 대해서 반복하며 세대 수를 누적해가면, 각 테스트케이스의 답이 된다.

✏ 코드 전문

#include<iostream>
#include<vector>
#include<algorithm>
 
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("input.txt", "r", stdin);
    for (int i = 1; i <= 10; i++) {
        int n;
        cin >> n;
        vector<int> arr;
        for (int j = 0; j < n; j++) {
            int temp;
            cin >> temp;
            arr.push_back(temp);
        }
 
        int count = 0;
        for (int j = 2; j < n-2; j++) {
            int cent = arr[j];
            if (arr[j - 2] < cent && arr[j - 1] < cent && arr[j + 1] < cent && arr[j + 2] < cent) {
                int m1 = max(arr[j - 2], arr[j - 1]);
                int m2 = max(arr[j + 1], arr[j + 2]);
                count += cent - (max(m1, m2));
            }
        }
 
        cout << "#" << i << " " << count << "\n";
    }
    return 0;
}