Bin_S+StudyRoom

• 문제

준호는 요즘 디펜스 게임에 푹 빠져 있습니다. 디펜스 게임은 준호가 보유한 병사 n명으로 연속되는 적의 공격을 순서대로 막는 게임입니다. 디펜스 게임은 다음과 같은 규칙으로 진행됩니다.

• 준호는 처음에 병사 n명을 가지고 있습니다.
• 매 라운드마다 enemy[i]마리의 적이 등장합니다.
• 병사 중 enemy[i]명 만큼 소모하여 enemy[i]마리의 적을 막을 수 있습니다.
  • 예를 들어 남은 병사가 7명이고, 적의 수가 2마리인 경우, 현재 라운드를 막으면 7 - 2 = 5명의 병사가 남습니다.
  • 남은 병사의 수보다 현재 라운드의 적의 수가 더 많으면 게임이 종료됩니다.
• 게임에는 무적권이라는 스킬이 있으며, 무적권을 사용하면 병사의 소모없이 한 라운드의 공격을 막을 수 있습니다.
• 무적권은 최대 k번 사용할 수 있습니다.
  준호는 무적권을 적절한 시기에 사용하여 최대한 많은 라운드를 진행하고 싶습니다.

준호가 처음 가지고 있는 병사의 수 n, 사용 가능한 무적권의 횟수 k, 매 라운드마다 공격해오는 적의 수가 순서대로 담긴 정수 배열 enemy가 매개변수로 주어집니다. 준호가 몇 라운드까지 막을 수 있는지 return 하도록 solution 함수를 완성해주세요.

• 제한 사항

1 ≤ n ≤ 1,000,000,000
1 ≤ k ≤ 500,000
1 ≤ enemy의 길이 ≤ 1,000,000
1 ≤ enemy[i] ≤ 1,000,000
enemy[i]에는 i + 1 라운드에서 공격해오는 적의 수가 담겨있습니다.
모든 라운드를 막을 수 있는 경우에는 enemy[i]의 길이를 return 해주세요.

• 입출력 예시

• 접근방식

우선 순위 큐가 떠올랐다. 우선 순위 큐란 간단히 말해서 큐와 같이 선입 선출의 자료구조이지만 우선 순위가 높은 데이터가 먼저 나가는 자료구조로 힙을 기반으로 구현되어 있다.

1. 우선 순위 큐를 오름 차순으로 선언 (top에 가장 작은 값)

2. enemy의 크기만큼 반복하면서 우선 순위 큐에 현재 순번 enemy를 담고

3. k의 개수보다 많이 쌓이면 answer에 우선 순위 큐 top을 더하고 pop 해준다

4. answer이 n보다 커지면 i (라운드) 반환

5. 모든 라운드 통과면 enemy의 크기 반환

• 코드

#include <vector>
#include <queue>

using namespace std;

int solution(int n, int k, vector<int> enemy)
{
    int answer = 0;
    
    priority_queue<int, vector<int>, greater<int>> pq;
    
    for (int i = 0; i < enemy.size(); i++)
    {
        pq.push(enemy[i]);
        
        if (pq.size() > k)
        {
            answer += pq.top();
            pq.pop();
        }
        
        if (answer > n)
        {
            return i;
        }
    }
    
    return enemy.size();
}

문제링크 :https://school.programmers.co.kr/learn/courses/30/lessons/142085

• 문제

길이가 같은 배열 A, B 두개가 있습니다. 각 배열은 자연수로 이루어져 있습니다.
배열 A, B에서 각각 한 개의 숫자를 뽑아 두 수를 곱합니다. 이러한 과정을 배열의 길이만큼 반복하며, 두 수를 곱한 값을 누적하여 더합니다. 이때 최종적으로 누적된 값이 최소가 되도록 만드는 것이 목표입니다. (단, 각 배열에서 k번째 숫자를 뽑았다면 다음에 k번째 숫자는 다시 뽑을 수 없습니다.)

예를 들어 A = [1, 4, 2] , B = [5, 4, 4] 라면

• A에서 첫번째 숫자인 1, B에서 첫번째 숫자인 5를 뽑아 곱하여 더합니다. (누적된 값 : 0 + 5(1x5) = 5)
• A에서 두번째 숫자인 4, B에서 세번째 숫자인 4를 뽑아 곱하여 더합니다. (누적된 값 : 5 + 16(4x4) = 21)
• A에서 세번째 숫자인 2, B에서 두번째 숫자인 4를 뽑아 곱하여 더합니다. (누적된 값 : 21 + 8(2x4) = 29)
  즉, 이 경우가 최소가 되므로 29를 return 합니다.

배열 A, B가 주어질 때 최종적으로 누적된 최솟값을 return 하는 solution 함수를 완성해 주세요.

• 제한 사항

배열 A, B의 크기 : 1,000 이하의 자연수
배열 A, B의 원소의 크기 : 1,000 이하의 자연수

• 입출력 예시

• 접근방식

1. A와 B의 두 수를 곱했을 때 가장 작은 값이 나와야 다 더했을 때 최솟값이 됨

2. A를 오름 차순 정렬, B를 내림 차순 정렬하고 곱하면 된다

• 코드

#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<int> A, vector<int> B)
{
    int answer = 0;

    sort(A.begin(), A.end());
    sort(B.rbegin(), B.rend());

    for (int i = 0; i < A.size(); i++)
    {
        answer += A[i] * B[i];
    }

    return answer;
}

문제링크 :https://school.programmers.co.kr/learn/courses/30/lessons/12941

• 문제

위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.

삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.

• 제한 사항

삼각형의 높이는 1 이상 500 이하입니다.
삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다.

• 입출력 예시

• 접근방식

1. 2차원 벡터 triangle을 표로 표현하면 아래와 같음

2. 표를 보면 i와 j의 위치를 가지고 본인 아래에 인접한 두 수를 찾을 수 있다. (왼쪽:i - 1, j) (오른쪽:i - 1, j - 1)

3. 임의의 2차원 배열(또는 벡터) dp를 정의하고 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + triangle[i][j] 인데

4. 해당 행에서 숫자가 제일 왼쪽인 경우( j == 0)와 제일 오른쪽인 경우(j == i)만 예외 처리를 해주면 된다

5. 반복문 끝에 dp[i][j] += triangle[i][j]를 해주어서 dp에 저장되어 있는 값 중 제일 큰 값으로 계산해도 되지만 answer과 dp[i][j]를 바로 비교해도 괜찮다

• 코드

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<vector<int>> triangle)
{
    int answer = 0;
    
    vector<vector<int>> dp;
    dp.assign(501, vector<int>(501, 0));
    
    dp[0][0] = triangle[0][0];
    
    for (int i = 1; i < triangle.size(); i++)
    {
        for(int j = 0; j <= i; j++)
        {
            if (j == 0) // 제일 왼쪽
            {
                dp[i][j] = dp[i - 1][j] + triangle[i][j];
            }
            else if (j == i) // 제일 오른쪽
            {
                dp[i][j] = dp[i - 1][j - 1] + triangle[i][j];
            }
            else
            {
                dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + triangle[i][j];
            }
            
            answer = max(answer, dp[i][j]);
        }
    }
    
    
    return answer;
}

문제링크 : https://school.programmers.co.kr/learn/courses/30/lessons/43105

• 문제

xx 회사의 2xN명의 사원들은 N명씩 두 팀으로 나눠 숫자 게임을 하려고 합니다. 두 개의 팀을 각각 A팀과 B팀이라고 하겠습니다. 숫자 게임의 규칙은 다음과 같습니다.

• 먼저 모든 사원이 무작위로 자연수를 하나씩 부여받습니다.
• 사원은 딱 한 번씩 경기를 합니다.
• 각 경기당 A팀에서 한 사원이, B팀에서 한 사원이 나와 서로의 수를 공개합니다. 그때 숫자가 큰 쪽이 승리하게 되고, 승리한 사원이 속한 팀은 승점을 1점 얻게 됩니다.
• 만약 숫자가 같다면 누구도 승점을 얻지 않습니다.

전체 사원들은 우선 무작위로 자연수를 하나씩 부여받았습니다. 그다음 A팀은 빠르게 출전순서를 정했고 자신들의 출전 순서를 B팀에게 공개해버렸습니다. B팀은 그것을 보고 자신들의 최종 승점을 가장 높이는 방법으로 팀원들의 출전 순서를 정했습니다. 이때의 B팀이 얻는 승점을 구해주세요.
A 팀원들이 부여받은 수가 출전 순서대로 나열되어있는 배열 A와 i번째 원소가 B팀의 i번 팀원이 부여받은 수를 의미하는 배열 B가 주어질 때, B 팀원들이 얻을 수 있는 최대 승점을 return 하도록 solution 함수를 완성해주세요.

• 제한 사항

A와 B의 길이는 같습니다.
A와 B의 길이는 1 이상 100,000 이하입니다.
A와 B의 각 원소는 1 이상 1,000,000,000 이하의 자연수입니다.

• 입출력 예시

• 접근방식

1. 우선 두 벡터를 오름 차순으로 정렬 해보기
2. aIndex와 bIndex를 0부터 시작해서 각각(aIndex, bIndex) 현재 A팀과 B팀의 크기보다 커지면 반복을 종료하는 반복문 시작
3. B팀의 현재 숫자가 A팀의 숫자보다 큰 경우, 승점 획득 > A팀과 B팀 모두 다음으로 넘어감 (A팀 index++, B팀 index++)
4. B팀의 현재 숫자가 A티므이 숫자보다 작은 경우, 해당 숫자 소모하고 B팀만 다음으로 넘어감 (B팀 index++)

• 코드

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<int> A, vector<int> B)
{
    int answer = 0;
    
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());
    
    int aIndex = 0;
    int bIndex = 0;
    
    while (aIndex < A.size() && bIndex < B.size())
    {
        if (A[aIndex] < B[bIndex])
        {
            answer++;
            aIndex++;
        }
        bIndex++;
    }
    
    return answer;
}

문제링크 : https://school.programmers.co.kr/learn/courses/30/lessons/12987

• 문제

자연수 n 개로 이루어진 중복 집합(multi set, 편의상 이후에는 "집합"으로 통칭) 중에 다음 두 조건을 만족하는 집합을 최고의 집합이라고 합니다.

1. 각 원소의 합이 S가 되는 수의 집합
2. 위 조건을 만족하면서 각 원소의 곱 이 최대가 되는 집합
예를 들어서 자연수 2개로 이루어진 집합 중 합이 9가 되는 집합은 다음과 같이 4개가 있습니다.
{ 1, 8 }, { 2, 7 }, { 3, 6 }, { 4, 5 }
그중 각 원소의 곱이 최대인 { 4, 5 }가 최고의 집합입니다.

집합의 원소의 개수 n과 모든 원소들의 합 s가 매개변수로 주어질 때, 최고의 집합을 return 하는 solution 함수를 완성해주세요.

• 제한 사항

최고의 집합은 오름차순으로 정렬된 1차원 배열(list, vector) 로 return 해주세요.
만약 최고의 집합이 존재하지 않는 경우에 크기가 1인 1차원 배열(list, vector) 에 -1 을 채워서 return 해주세요.
자연수의 개수 n은 1 이상 10,000 이하의 자연수입니다.
모든 원소들의 합 s는 1 이상, 100,000,000 이하의 자연수입니다.

• 입출력 예시

• 접근방식

1. 각 원소의 합이 s, 즉 겹치지 않는 원소의 곱이 최대가 되는 집합을 찾으면 됨
2. 해당 집합은 n와 s를 나누기와 모듈러 연산을 통하여 구한다
3. s / n 으로 나눈 해당 숫자를 n개 만큼 생성후
4. s % n 으로 나운 숫자를 각각에 더해준다
5. 단, 만들 수 없는 경우는 (n > s) -1만 담고 return

• 코드

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> solution(int n, int s)
{
    vector<int> answer;
    
    if (n > s)
    {
        answer.push_back(-1);
        return answer;
    }
    
    int divideNumber = s / n;
    
    answer.assign(n, divideNumber);
    
    int modulerNumber = s % n;
    
    for (int i = 0; i < answer.size() && modulerNumber > 0; i++)
    {
        answer[i]++;
        modulerNumber--;
    }
    
    sort(answer.begin(), answer.end());
    return answer;
}

문제링크 : https://school.programmers.co.kr/learn/courses/30/lessons/12938

• 문제

괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어
"()()" 또는 "(())()" 는 올바른 괄호입니다.
")()(" 또는 "(()(" 는 올바르지 않은 괄호입니다.
'(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요.

• 제한 사항

문자열 s의 길이 : 100,000 이하의 자연수
문자열 s는 '(' 또는 ')' 로만 이루어져 있습니다.

• 입출력 예시

• 접근방식

1. s에서 '('가 나오면 스택에 push
2. 만약 다른 문자 ( ')' )가 나오고 스택에 요소가 존재하면 pop
3. 그 외의 것은 false 출력
4. 반복문이 끝난 후 스택이 남아 있지 않으면 true 출력

• 코드

#include <string>
#include <iostream>
#include <stack>

using namespace std;

bool solution(string s)
{
    bool answer = false;
    stack<char> stk;
    for (int i = 0; i < s.length(); i++)
    {
        if (s[i] == '(')
        {
            stk.push(s[i]);
        }
        else if (stk.size())
        {
            stk.pop();
        }
        else
        {
            return answer;
        }
    }

    if (!stk.size())
    {
        answer = true;
    }

    
    return answer;
}

문제링크 : https://school.programmers.co.kr/learn/courses/30/lessons/12909

• 문제

회사원 Demi는 가끔은 야근을 하는데요, 야근을 하면 야근 피로도가 쌓입니다. 야근 피로도는 야근을 시작한 시점에서 남은 일의 작업량을 제곱하여 더한 값입니다. Demi는 N시간 동안 야근 피로도를 최소화하도록 일할 겁니다.Demi가 1시간 동안 작업량 1만큼을 처리할 수 있다고 할 때, 퇴근까지 남은 N 시간과 각 일에 대한 작업량 works에 대해 야근 피로도를 최소화한 값을 리턴하는 함수 solution을 완성해주세요.

• 제한 사항
  • works는 길이 1 이상, 20,000 이하인 배열입니다.
  • works의 원소는 50000 이하인 자연수입니다.
  • n은 1,000,000 이하인 자연수입니다
• 입출력 예시

• 접근방식

n만큼 반복 하면서 벡터를 내림 차순으로 정렬 후 가장 높은 수 만큼 빼는 것으로 접근

1. n이 0이 될 때 까지 반복하다가 n이 0이 되거나 내림 차순으로 정렬한 벡터의 맨 앞(Max 값)이 0이면 반복 종료

2. works에서 front를 미리 뽑아 놓고 works의 벡터를 순회해서 미리 뽑아 놓은 front와 해당 순차의 works값이 같으면 n값과 함께 빼주기

3. 그렇지 않고 works의 다음 값이 있으면 다시 내림 차순 정렬, 해당 반복문 종료

4.  works에 남아 있는 값 제곱해서 answer에 더해주기

• 코드

#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

long long solution(int n, vector<int> works)
{
    long long answer = 0;
    
    sort(works.rbegin(), works.rend());

    while(n)
    {
        if (!works.front())
        {
            break;
        }
        
        int front = works.front();
        
        for (int i = 0; i < works.size(); i++)
        {
            if (!n)
            {
                break;
            }
            
            if (front == works[i])
            {
                works[i]--;
                n--;
            }
            else
            {
                if (i != works.size() - 1)
                {
                    if (works[i] < works[i + 1])
                    {
                        sort(works.rbegin(), works.rend());
                    }
                    break;
                }
            }
        }
    }
    
    for (int i = 0; i < works.size(); i++)
    {        
        answer += pow(works[i], 2);
    }
    
    return answer;
}

• 문제링크 : https://school.programmers.co.kr/learn/courses/30/lessons/12927

• 문제

강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경우에는 강의의 흐름이 끊겨, 학생들이 대혼란에 빠질 수 있기 때문이다. 즉, i번 강의와 j번 강의를 같은 블루레이에 녹화하려면 i와 j 사이의 모든 강의도 같은 블루레이에 녹화해야 한다.

강토는 이 블루레이가 얼마나 팔릴지 아직 알 수 없기 때문에, 블루레이의 개수를 가급적 줄이려고 한다. 오랜 고민 끝에 강토는 M개의 블루레이에 모든 기타 강의 동영상을 녹화하기로 했다. 이때, 블루레이의 크기(녹화 가능한 길이)를 최소로 하려고 한다. 단, M개의 블루레이는 모두 같은 크기이어야 한다.

강토의 각 강의의 길이가 분 단위(자연수)로 주어진다. 이때, 가능한 블루레이의 크기 중 최소를 구하는 프로그램을 작성하시오.

• 입력

첫째 줄에 강의의 수 N (1 ≤ N ≤ 100,000)과 M (1 ≤ M ≤ N)이 주어진다. 다음 줄에는 강토의 기타 강의의 길이가 강의 순서대로 분 단위로(자연수)로 주어진다. 각 강의의 길이는 10,000분을 넘지 않는다.

• 출력

첫째 줄에 가능한 블루레이 크기중 최소를 출력한다.

• 예제 입력

9 3
1 2 3 4 5 6 7 8 9

• 예제 출력

17

• 접근방식

범위를 봤을때 10만인데 단순 2중 for문으로 하면 시간 복잡도가 n^20만이라 이분 탐색으로 접근했다.

블루레이에 하나씩 담는 처리를 할건데 담는 처리는 중앙 값에서 값을 하나씩 빼는 것으로 처리하고
중앙 값에서 요소의 값을 빼면서 진행하는데 0보다 작다면 (음수가 된다면) 중앙 값을 바꾸고 블루레이 갯수를 추가하는 식으로 했다.

• 코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int n, m, a[100004], low, high, mid, sum, _max, result;

bool check(int mid)
{
    if (_max > mid)
    {
        return false;
    }
    int num = mid;
    int cnt = 0;
    for (int i = 0; i < n; i++)
    {
        if (mid - a[i] < 0)
        {
            mid = num;
            cnt++; // 블루레이 갯수 증가
        }
        mid -= a[i]; // 블루레이에 담음
    }
    if (mid != num)
    {
        cnt++;
    }
    return cnt <= m;
}

int main()
{
    cin >> n >> m;

    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        sum += a[i];
        _max = max(_max, a[i]);
    }
    low = 0, high = sum;
    while (low <= high)
    {
        mid = (low + high) / 2;
        if (check(mid))
        {
            high = mid - 1;
            result = mid;
        }
        else
        {
            low = mid + 1;
        }
    }

    cout << result;

    return 0;
}

• 문제링크 : https://www.acmicpc.net/problem/2776