[백준 1744] 수 묶기

문제 링크 => 1744번: 수 묶기 (acmicpc.net)

1744번: 수 묶기

 

그리디 알고리즘 문제이다.

 

어떤 수열이 {0, 1, 2, 4, 3, 5}일 때, 그냥 이 수열의 합을 구하면 0+1+2+4+3+5 = 15이다.

하지만, 2와 3을 묶고, 4와 5를 묶게 되면, 0+1+(2*3)+(4*5) = 27이 되어 최대가 된다.

수열의 모든 수는 단 한번만 묶거나, 아니면 묶지 않아야한다.

수열이 주어졌을 때, 수열의 각 수를 적절히 묶었을 때, 그 합이 최대가 되게 하도록 해야 한다.

 

문제 자체는 쉬워보이는데 숨어있는 case를 찾아내느라 좀 힘들었다.

문제 접근 방법은 다음과 같다.

 

1. 배열 x는 [-1000, 0] 범위에 해당하도록 잡고, 범위 y는 [1, 1000] 범위에 해당하도록 잡는다.

    처음에 구현할 때 음수, 양수 따로 잡고 0은 무시했었는데 다음과 같은 케이스를 고려하지 못했다.

    {-3, -2, -1, 0} 에 대해서 (-3)*(-2) + (-1)*(0) = 6 으로 만들어야 하는데 이전에 만들었던 방법으로는

    (-3)*(-2) + (-1) = 5 가 되는 바람에 틀렸다.

 

2. 배열 x, y에 대하여 절댓값 기준으로 내림차순 정렬을 한다.

     greedy하게 큰 수 부터 곱해가는 매커니즘을 활용하였다.

 

3. 다음과 같이 두 수를 묶어가면서 곱한 값들을 전부 더한다.

 

 

i번째 원소와 i+1번째 원소에 대해서

1. x[i] * x[i+1] > x[i] + x[i+1] 일 경우 묶어주고 더해주며 i 값을 1 증가 시킨다. (for-loop 에서 2칸 pass)

2. x[i] * x[i+1] <= x[i] + x[i+1] 일 경우 묶지 않고 자기 자신만을 더한다.

 

 

Solution Code

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>

using namespace std;

bool compare(int x, int y) {
	return x > y;
}

int solution(int* A, int N) 
{
	int i, j, k, result, x_cnt, y_cnt;
	int* x, *y;
	
	x_cnt = y_cnt = 0;
	for (i = 0; i < N; i++) {
		if (A[i] > 0) x_cnt++;
		else if (A[i] <= 0) y_cnt++;
	}

	x = (int*)malloc(sizeof(int) * x_cnt);
	y = (int*)malloc(sizeof(int) * y_cnt);

	for (i = 0, j = 0, k = 0; i < N; i++) {
		if (A[i] > 0) x[j++] = A[i];
		else if (A[i] <= 0) y[k++] = A[i];
	}

	sort(x, x + x_cnt, compare);
	sort(y, y + y_cnt);
	result = 0;
	for (i = 0; i < x_cnt; i++) {
		if (i == x_cnt - 1) {
			result += x[i];
		}
		else {
			if (x[i] * x[i + 1] > x[i] + x[i + 1])
				result += x[i] * x[i + 1], i++;
			else
				result += x[i];
		}
	}
	for (i = 0; i < y_cnt; i++) {
		if (i == y_cnt - 1) {
			result += y[i];
		}
		else {
			if (y[i] * y[i + 1] > y[i] + y[i + 1])
				result += y[i] * y[i + 1], i++;
			else
				result += y[i];
		}
	}

	if(x_cnt) free(x);
	if(y_cnt) free(y);

	return result;
}

int main()
{
	int i, N, A[50];
	
	scanf("%d", &N);
	for (i = 0; i < N; i++)
		scanf("%d", &A[i]);

	printf("%d", solution(A, N));

	return 0;
}