BOJ 1744: 수 묶기

#BOJ 1744: 수 묶기

1744번: 수 묶기

#풀이

그리디 연습하려고 푸는 문제인데 내가 그리디로 푸는 것인지 잘 모르겠다... 그냥 최선의 선택을 하려고 하는데 그냥 평소와 같이 생각하는 거 같다...

 

일단 이 문제는 괄호치는 거랑 비슷하다.

 

그래서 일단 조건이 

1.양수*양수

2.음수*음수

3.양수*0

4.음수*0

있다.  이 중에서 괄호를 쳐하는 상황은 1,2,4 이어야 괄호를 쳐서 최대의 값을 만들 수 있다.

 

일단 정렬을 해서 뒤에서 부터 2개씩 숫자를 묶고 0을 만났을 때

 

다시 인덱스 처음으로 돌아가서 앞에서 2개씩 묶는다.

그러는 이유가 2번이 문제인데 음수 * 음수 는 양수가 되므로 가장 작은 수끼리 곱해야 가장 큰 수 가 나온다.

 

또한 인덱스 를 뒤에서 부터 오는 경우는 1*1을 괄호로 묶지 않도로 해야한다. 그냥 인덱스값이 1보다 클 때 괄호로 묶으면!

 

그리고 음수는 음수* 0 을 생각해야하는데 이것도 쉽다.

 

항상 문제를 풀 때 조건을 먼저 생각하게 되는데 뭔가 평소랑 다를 거 없이 풀어서 내가 그리디로 풀 고 있는지 뭔가 의심이 간다!! 나도 잘하고 싶다~~ minbear 우승!!

 

#코드

#include<iostream>
#include<algorithm>
using namespace std;

int n;
int arr[52];
int ans;
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;

	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
	}
	arr[0] = 1; //arr[1]*arr[0] == arr[1] 를 유지
	arr[n + 1] = 1; //arr[n]*arr[n+1] == arr[n] 를 유지
	sort(arr + 1, arr + n+1);
	int j = 0; // 0부터 음수 까지
	for (int i = n; i >= 1; i--) { // 양수 뒤에서 부터 2개씩 묶음
		if (arr[i] > 1 && arr[i - 1] > 1)
		{
			ans = ans + arr[i] * arr[i - 1];
			i--;
		}
		else if (arr[i] <= 0)
		{
			j = i;
			break;
		}
		else
			ans = ans + arr[i];

	}
	// 음수
	for (int i = 1; i <= j; i++) { // 앞에서 부터 2개씩 묶음
		if (arr[i] < 0 && arr[i + 1] < 0)
		{
			ans = ans + arr[i] * arr[i + 1];
			i++;
		}
		else if (arr[i] < 0 && arr[i + 1] == 0)
		{
			i++;
		}
		else
			ans = ans + arr[i];
	}
	cout << ans << '\n';
	return 0;
}