[C++][백준 BOJ]1744_수 묶기.

문제 번호

https://www.acmicpc.net/problem/1744

1744번: 수 묶기

 

 

 

알고리즘 분류

 그리디(greedy), 정렬

 

문제 풀이

 문제에서 주어진 수열을 오름차순으로 정렬한다. 합을 가장 크게 만드는게 목표이기 때문에 양수는 가장 큰 수 끼리

묶어서 더해야하고 음수는 가장 작은 수 끼리 묶어서 더해야한다. 그래서 양수부분의 합, 음수부분의 합을 구한다음 bool 형태의 visited 배열을 선언하여서  남은 수 들을 더해주기로하였다.

 

문제에서 주어진 수열을 오름차순으로 정렬한다.

sort(number.begin(), number.end());

양수부분의 합을 구한다.

// 양수 부분 구하기.
    for(int i=number.size()-1; i>0; i--)
    {        
        if( (!visitd[i] && !visitd[i-1]) && (number[i]>1 && number[i-1] >1) )
        {
            visitd[i] = visitd[i-1] = true;
            answer += number[i]*number[i-1];
        }
    }

음수부분의 합을 구한다.

// 음수 부분 구하기.
    for(int i=0; i<number.size()-1; i++)
    {
        if( (!visitd[i] && !visitd[i+1]) && (number[i]<=0 && number[i+1]<=0) )
        {
            visitd[i] = visitd[i+1] = true;
            answer += number[i]*number[i+1];
        }
    }

그리고 남겨진 수 들을 더해준다.

// 남겨진 수들 더하기.
      for(int i=0; i<number.size(); i++)
      {
          if( !visitd[i] )
              answer += number[i];
      }

전체 코드

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

bool visitd[10001] = {false};

long long Solution(vector<int> &number)
{
    long long answer=0;

    sort(number.begin(), number.end());
    
    // 양수 부분 구하기.
    for(int i=number.size()-1; i>0; i--)
    {        
        if( (!visitd[i] && !visitd[i-1]) && (number[i]>1 && number[i-1] >1) )
        {
            visitd[i] = visitd[i-1] = true;
            answer += number[i]*number[i-1];
        }
    }

    // 음수 부분 구하기.
    for(int i=0; i<number.size()-1; i++)
    {
        if( (!visitd[i] && !visitd[i+1]) && (number[i]<=0 && number[i+1]<=0) )
        {
            visitd[i] = visitd[i+1] = true;
            answer += number[i]*number[i+1];
        }
    }

    // 남겨진 수들 더하기.
    for(int i=0; i<number.size(); i++)
    {
        if( !visitd[i] )
            answer += number[i];
    }
    
    return answer;
}

void Insert(vector<int> &number, int N)
{
    for(int i=0; i<N; i++)
    {
        int num; cin >> num;
        number.push_back(num);
    }
}

int main()
{
    int N; cin >> N;
    vector<int> number;
    Insert(number,N);
    cout << Solution(number);

    return 0;
}

특이사항

 양수부분의 더할때 1은 다른수와 곱하는것보다 그냥 더해주는것이 더 큰 수 를 만들 수 있다.

문제에서 주어진 수열의 각 숫자들은 int 범위를 넘어가지 않지만 수열의 합은 int 범위를 넘어갈 수 있기 때문에

long long 타입으로 선언해주었다.

 

그리고 글쓰기 하면서 알았는데 visited 배열이름을 틀렸다.....