M'S Blog

M'S Blog

WWDC20 student challenge Winner!

백준 1744 - 수 묶기

최대 1 분 소요

문제

백준 1744 - 수 묶기 풀러가기

문제 분석

수열이 주어지고, 수열의 최대 합을 구해야 한다.

이때, 수열은 두 수가 최대 한번 묶여 질 수가 있다.(곱한다는 뜻)

곱했을 때 값을 최대로 만들어서 더하면 되므로 큰 수 두개끼리 곱해주면 된다.

  • 6 5 4 가 있다면
    • 6+5+4 보다
    • 6*5 +4 가 더 크다.

근데 음수가 있다면?

  • 작은 순으로 곱해주면 된다.
  • 1 -9 -8
    • (-8*-9) + 1

1이 있다면, 1은 묶는 것 보다 그냥 더하는 게 더 낫다.

  • 1 1 1 1 이 있다면 두개씩 묶어서 1+1이 되는 것 보다 1이 4개로 더해지는 것이 더 낫다.

0이 있다면, 무시하면 된다. 이때, 음수가 홀수개라서 짝이 지어지지 않는 경우에는 음수랑 묶으면 된다.

문제 풀이(C++)

  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
    74
    75
    76
    #include <cstdio>
    #include <vector>
    #include <algorithm>
     
    using namespace std;
     
    vector<int> positive;
    vector<int> negative;
     
    int main() {
     
        int n;
     
        int sum = 0;
     
        int zeroCount = 0;
     
        scanf("%d", &n);
     
        for (int i = 0; i < n; i++) {
            int temp;
            scanf("%d", &temp);
     
            if (temp >= 0) {
                positive.push_back(temp);
                if (temp == 0) {
                    zeroCount++;
                }
            }
            else {
                negative.push_back(temp);
            }
            
        }
     
        sort(positive.begin(), positive.end(),[](int x, int y) {
            return x > y;
            });
     
        sort(negative.begin(), negative.end());
     
        for (int i = 0; i < positive.size();i++) {
            if (positive[i] != 1 && positive[i] != 0) {
                if (i+1 < positive.size() && positive[i + 1] != 1 && positive[i + 1] != 0) {
                    sum += (positive[i] * positive[i + 1]);
                    i++;
                }
                else {
                    sum += positive[i];
                }
            }
            if (positive[i] == 1) {
                sum++;
            }
        }
     
        for (int i = 0; i < negative.size(); i++) {
            if (i + 1 < negative.size()) {
                sum += (negative[i] * negative[i + 1]);
                i++;
            }
            else {
                if (zeroCount > 0) { 
                    zeroCount--;
                    continue; 
                }
                else if (zeroCount == 0) {
                    sum += negative[i];
                }
            }
        }
     
        printf("%d", sum);
     
        return 0;
    }
    		cs
    • 7, 8번째 줄 : 음수와 양수를 나눠서 받는다.
    • 24~32번째 줄 : 음수와 양수를 나눠서 벡터에 입력한다.
      • 생각해보니까 이때 0과 1은 굳이 벡터에 넣어줄 필요 없이 변수에 0과 1의 개수만 나타내줘도 좋을 것 같다.
    • 36번째 줄: 양수를 내림차순으로 정렬해준다.





아직 배움의 과정에 있는 학생이니 내용에 부족한 점이 보이면 지적은 하되, 비난은 하지 말아주세요!!

댓글남기기

참고