뚝딱뚝딱

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

난이도⭐⭐⭐

✅ 문제 풀이

• 이 문제의 핵심은 굳이 100*100의 배열에 입력을 저장할 필요 없이, 입력을 받으면서 누적합을 구하고, max를 갱신해 나가면 된다는 것이다.
• 입력을 받을 때, 행을 기준으로 열들을 받는다. 따라서 2중 for문을 사용한다.
• 2중 for문에서 행이 먼저 돌기 때문에, 한 행의 값을 입력받을 때 100개의 열 값을 받는다.
• 따라서 row는 각 행마다 누적합을 구하고, 현재의 max와 비교해서 큰 값을 갱신한다.
• col은 각 행마다 한번에 100개씩 주어진다. 따라서 크기가 100인 배열을 선언해서, 해당 열에 누적하도록 하였다.
• 열의 최대값은 2중 for문이 끝난 후, 구해진 누적값들을 서로 비교해 최대를 가리고, 현재의 max와 비교해 갱신한다.
• 대각선은, 2중 for문에서 현재의 행과 열이 같은 값이면(if) 오른쪽방향 대각선의 누적합에, 행과 열을 더했을 때 99이면(else if) 왼쪽방향 대각선의 누적합에 더하도록 하였다. 마찬가지로 2중 for문이 끝난 후 두 값중 max를 구하고, 현재의 max와 비교해 갱신한다.
• 최종 max를 출력한다.

✏ 코드 전문

#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 = 0; i < 10; i++) {
		int t;
		cin >> t;//test case number

		vector<int> col(100,0);
		int rcross = 0;
		int lcross = 0;

		int m = 0;

		for (int j = 0; j < 100; j++) {
			int row = 0;
			for (int k = 0; k < 100; k++) {
				int temp;
				cin >> temp;
				row += temp;
				col[k] += temp;
				if (j == k) rcross += temp;
				else if ((j + k) == 99) lcross += temp;
			}
			m = max(m, row);
		}
		
		for (int j = 0; j < 100; j++) {
			m = max(m, col[j]);
		}

		m = max(m, max(rcross, lcross));
		
		cout << "#" << t << " " << m << "\n";

	}
	return 0;
}

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;
}