출처: https://cses.fi/problemset/task/1642

문제 설명

You are given an array of n integers, and your task is to find four values (at distinct positions) whose sum is x.

입력 

The first input line has two integers n and x: the array size and the target sum.

The second line has n integers a_1,a_2,…,a_n: the array values.

출력 

Print four integers: the positions of the values. If there are several solutions, you may print any of them. If there are no solutions, print IMPOSSIBLE.

입력 예

8 15
3 2 5 8 1 3 2 3

출력 예

2 4 6 7

제약조건

  • 1 <= n <= 1000
  • 1 <= x, a_i <= 10^9

문제 풀이 내용

서로 다른 배열의 원소 2개의 합으로 새로운 배열을 만든다. 그러면 배열에서 2개의 합으로 원하는 수를 만드는 문제로 바꿀 수 있다. (참고) 다만, 원래 배열에서 4개의 원소가 달라야 하는 조건을 확인해야 한다.

프로그램 내용

더보기 
...
    vector <tuple <long, int, int> > num_arr;

    for(int idx=0; idx < nNum; ++idx)
        int temp;
        in_num.push_back(temp);

    for(int idx=0; idx < nNum-1; ++idx)
        for(int id = idx+1; id < nNum ; ++ id)
            num_arr.push_back(make_tuple(in_num[idx]+in_num[id], idx+1, id+1));

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

    int id = 0, idx = num_arr.size()-1;
    while( id < idx )
        long a, b, c, d, e, f;
        tie(a, b, c) = num_arr[id];
        tie(d, e, f) = num_arr[idx];
        long k = a+d;

        if (k == tSum)
            if ( b == e || c == f)
                break;
            else
                cout << b << " " << c << " " << e << " " << f << endl;
        else if ( k < tSum) id++;
        else idx--;
...

 

Sorting and Searching ( link )

저작자표시 비영리 동일조건

'CSES' 카테고리의 다른 글

CSES 2. Subarray Sums I (1660)  (0) 2019.10.03
CSES 2. Nearest Smaller Values (1645)  (0) 2019.10.03
CSES 2. Sum of Three Values (1641)  (0) 2019.10.02
CSES 2. Reading Books (1632)  (0) 2019.10.02
CSES 2. Factory Machines (1620)  (0) 2019.10.01

출처: https://cses.fi/problemset/task/1641

문제 설명

You are given an array of n integers, and your task is to find three values (at distinct positions) whose sum is x.

입력 

The first input line has two integers n and x: the array size and the target sum.

The second line has n integers a_1,a_2,…,a_n : the array values.

출력

Print three integers: the positions of the values. If there are several solutions, you may print any of them. If there are no solutions, print IMPOSSIBLE.

입력 예

4 8
2 7 5 1

출력 예

1 3 4

제약조건

  • 1 <= n <= 5000
  • 1 <= x, a_i <= 10^9

문제 풀이 

첫번째 수를 고정하고, 필요한 수에서 그 수만큼을 빼내면, n-1 배열에서 2개의 합으로 (x - a_i)를 만드는 문제가 된다. 참고

프로그램 내용

더보기 
...
    vector <pair <long, long> > num_arr;

    for(int idx=0; idx < nNum; ++idx)
        int temp;
        num_arr.push_back({temp, idx+1});

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

    for (int a=0; a < nNum-2; ++a)
        int b = a+1 , c = nNum-1;
        int ttSum = tSum - num_arr[a].first;
        while( b < c )
            int k = num_arr[b].first + num_arr[c].first;

            if (k == ttSum)
                cout << num_arr[a].second << " " << num_arr[b].second << " " << num_arr[c].second << endl;
            else if ( k < ttSum) b++;
            else c--;
...

 

Sorting and Searching ( link )

저작자표시 비영리 동일조건

'CSES' 카테고리의 다른 글

CSES 2. Nearest Smaller Values (1645)  (0) 2019.10.03
CSES 2. Sum of Four Values (1642)  (0) 2019.10.02
CSES 2. Reading Books (1632)  (0) 2019.10.02
CSES 2. Factory Machines (1620)  (0) 2019.10.01
CSES 2. Room Allocation (1164)  (0) 2019.10.01

출처: https://cses.fi/problemset/task/1631

문제 설명

There are n books, and Kotivalo and Justiina are going to read them all. For each book, you know the time it takes to read it.

They both read each book from beginning to end, and they cannot read a book at the same time. What is the minimum total time required?

입력  

The first input line has an integer n: the number of books.

The second line has n integers t_1,t_2,…,t_n : the time required to read each book.

출력  

Print one integer: the minimum total time.

입력 예

3
2 8 3

출력 예

16

제약조건

  • 1 <= n <= 2x10^5
  • 1 <= t_i <= 10^9

문제 풀이 

가장 긴책을 읽는 동안 다른 책들을 모두 읽을 수 있으면, 가장 긴책을 읽는 시간 * 2, 아니면, 나머지 책을 읽는 시간 + 가장 긴책을 읽는 시간이 된다.

프로그램 내용

더보기 
...
    for (int idx = 0; idx < nBook; idx++)
        long temp=0;
        lBook = max(lBook, temp);
        sumTime += temp;

    if ( lBook > (sumTime - lBook) )
        mTime = 2 * lBook;
    else
        mTime = sumTime;
...

 

Sorting and Searching ( link )

저작자표시 비영리 동일조건

'CSES' 카테고리의 다른 글

CSES 2. Sum of Four Values (1642)  (0) 2019.10.02
CSES 2. Sum of Three Values (1641)  (0) 2019.10.02
CSES 2. Factory Machines (1620)  (0) 2019.10.01
CSES 2. Room Allocation (1164)  (0) 2019.10.01
CSES 2. Traffic Lights (1163)  (0) 2019.10.01

+ Recent posts

티스토리툴바