백준 1744 수 묶기

작성일 | In |

Problem : 수 묶기

유형 : 그리디, DP

문제 해석

  • 수를 합이 최대가 되도록 묶은 결과 값을 내놓아라.

문제 재해석

  • 숫자는 두개씩 묶은 다음 더해질 수 있다.
  • 묶을 때의 위치는 상관이 없다.
  • 묶지 않을 수 있다.

해결 전략

  • 정렬한 뒤 예외를 설정하며, 곱하거나 더해 나가면 된다.
  • 음수인 경우, 가장 작은 숫자 끼리 계속 곱해나가고 더한다.
  • 0인 경우, 이전에 음수가 있었다면 곱해서 0 으로 만들어 준다.
  • 양수인 경우
    • 1 의 경우에는 곱하면 손해이므로, 그냥 더해준다.
    • 가장 큰 숫자끼리 계속 곱해나가고 더한다.
  • 이 과정은 최선의 선택을 계속 찾아 나가는 것이다.

설계, 구현

  • 정렬을 한다.
  • 적절히 예외 처리를 해준다.
  • 음수, 양수(1이 아닌 경우)에서 연속으로 짝수 개가 등장한 경우, 곱해주고 더해준다.

주의할 점

  • 정렬을 하고 나면, 큰 양수는 뒤쪽에 있다.
  • 앞에서 곱해 나가면, 양수 중 작은 것들 끼리 곱하게 된다.
  • 홀수개로 끝나 마지막에 남아있는 수가 있을 수 있다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <bits/stdc++.h>
#define ll long long
using namespace std;

int n;
vector<ll> vec, positive_vec;

int positive_cnt, negative_cnt;
ll answer, cur;

void Positive(ll &num) {
    if (cur < 0) {
        answer += cur;
        cur = 0;
    }
    if (num == 1) {
        answer += num;
        return;
    }
    
    positive_cnt++;
    if (positive_cnt % 2 != 0) cur = num;
    else {
        answer += num * cur;
        cur = 0;
    }
}

void Negative(ll& num) {
    negative_cnt++;
    if (negative_cnt % 2 != 0) cur = num;
    else {
        answer += num * cur;
        cur = 0;
    }
}

void Solve() {
    for (ll &num : vec) {
        if (num < 0) Negative(num);
        else if (num == 0) cur = 0;
        else positive_vec.push_back(num);
    }

    for (auto it = positive_vec.rbegin(); it != positive_vec.rend(); ++it) {
        Positive(*it);
    }

    answer += cur;
    cout << answer << "\n";
}

void Input() {
    cin >> n;
    vec.resize(n);

    for (ll& num : vec) {
        cin >> num;
    }
    sort(vec.begin(), vec.end());
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);  cout.tie(NULL);
    freopen("input.txt", "r", stdin);

    Input();
    Solve();

    return 0;
}

피드백

  • 정렬한 뒤, 음수처럼 앞에서 부터 곱해나가 오답이 나왔었다.
  • 큰수끼리 곱한다는 조건을 정렬한 뒤 잊은 것이다.
  • 사실, 음수를 보관하는 벡터, 양수를 보관하는 벡터를 따로 관리하며 구현하는 방법이 실수도 없었을 것 같고 더 구현이 쉬웠을 것 같다.
  • 다른 분들 풀이를 보니 DP 로도 해결할 수 있었다.