mojo's Blog
[백준 1744] 수 묶기 본문
문제 링크 => 1744번: 수 묶기 (acmicpc.net)
그리디 알고리즘 문제이다.
어떤 수열이 {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;
}
'백준 > Greedy' 카테고리의 다른 글
띄어쓰기를 포함한 문자열을 입력 (0) | 2022.01.05 |
---|---|
[백준 1339] 단어 수학 (0) | 2021.11.11 |
[백준 19541] 역학 조사 (0) | 2021.07.17 |
[백준 19539] 사과나무 (0) | 2021.07.17 |