[구름] 직사각형 만들기 C++

https://level.goorm.io/exam/163680/%EC%A7%81%EC%82%AC%EA%B0%81%ED%98%95-%EB%A7%8C%EB%93%A4%EA%B8%B0/quiz/1

구름LEVEL

 

 

풀이

 

그리디 알고리즘 활용

 

1. 직사각형을 만들기 위해서 필요한 막대는 4개

2. 같은 길이의 막대 2개를 한 세트로, 두 세트가 필요

3. 같은 길이의 막대가 4개 이상이면 정사각형 만들기 가능

 

!! 길이가 긴 막대부터 차례로 직사각형을 만들어 나가는 것이 만들 수 있는 직사각형 넓이의 합의 최대값 !!

 

처음엔 map에 key값에 막대 길이, value값에 막대 개수를 저장하고 iterator로 탐색하며 사각형을 구현하도록 코드를 작성했는데, Time out 발생

 

>> 

입력값의 최대 크기인 10의 6승만큼 크기를 가진 input 배열을 선언하고 해당 배열의 인덱스를 막대기의 길이로, 인덱스의 값을 막대기의 개수로 대입하여 사용

 

** input 배열을 전역변수로 선언하여 Time out 방지

 

input 배열 뒤부터 길이가 긴 순으로 탐색

막대가 2개 이상이라면 킵하고

그 이후에 2개 이상 막대가 발견되면 이전의 막대와 직사각형을 만들어 넓이 계산 후 answer에 더함

-- 반복

 

 

 

long long input[1000000] = { 0, };	// 막대 길이와 막대 개수 정보를 담을 배열 전역변수 선언
// index : 막대 길이
// input[index] : index 길이의 막대 개수
	int main() {

		int n;	// 입력값
		cin >> n;

		long long answer = 0;
		bool flag = true;	// 개수가 2 이상인 막대가 선택됬을 때, 이전에 이미 선택 된 막대가 있는지 판단하는 변수

		int curVal = 0;

		// 반복문으로 input에 막대 개수 정보 입력
		for (int i = 0; i < n; i++) {
			int temp;
			cin >> temp;
			input[temp]++;
		}
		
        // 길이가 긴 순으로 탐색
		for (long long i = 1000000; i > 0; i--) {
			// 만약 막대의 개수가 2개 이상이고
			if (input[i] >= 2) {
				// 이전에 선택된 막대가 없다면
            			if (flag) {
					curVal = i;	// curVal에 막대의 길이 저장
					flag = false;
				}
                // 이전에 선택된 막대가 있다면
				else {
					answer = answer+ (curVal * i);	// 이전에 선택된 막대와 현재 막대를 곱해서 넓이 계산
					flag = true;
				}
				input[i] -= 2;	// 막대의 개수 2개 감소
				i++;	// 예를 들어 현재 막대가 4개일 경우 같은 길이의 막대를 4개 사용하여 사각형을 만들 수 있기 때문에 현재 막대를 한 번 더 탐색하기 위한 i값 1 증가
			}
		}
		cout << answer << endl;
	}