2024 부산대학교 프로그래밍 대회 (PNUPC) - UPSOLVING

대회 날짜 : 2024년 5월 4일

 

A. 모험의 시작 ( UPSOLVING ) Bronze Ⅲ

문제 바로가기 (클릭시 이동)

시간 제한 1초 / 메모리 제한 917 MB

 

PULSE를 떠나게 된 산지니 4인조는 저금통에 조금씩 모아둔 돈을 가지고 모험을 떠나기로 했다.

모험을 떠나기 위해서는 문지기 후안과의 대결에서 이겨야 한다. 문지기 후안을 이기려면 후안의 공격력보다 높은 무기를 가지고 있어야 한다. 그래서 4인조는 문지기 후안과 대결하기 전에 상점에서 무기를 구매하려고 한다. 4인조는 상점에서 판매하는 𝑁개의 무기 중 하나만을 구매할 수 있으며 4인조가 가진 돈 𝑋보다 비싼 무기는 구매할 수 없다. 산지니 4인조가 후안을 이기고 모험을 떠날 수 있을지 알아보자!

 

CODE - C++

#include <iostream>
using namespace std;
int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    short N;
    int X,S,M=0;
    cin >> N >> X >> S;
    while(N--){
        int c,p;
        cin >> c >> p;
        if (c<=X && M<p){
            M=p;
        }
    }
    if (M>S) cout << "YES";
    else cout << "NO";
    return 0;
}

이 문제는 X보다 작거나 같은 가격을 가진 가장 공격력이 높은 무기가 후안의 공격력보다 높은 지를 구하는 문제다.

N번 반복문을 돌면서 c가 X보다 작거나 같고 p가 M보다 크다면 M을 수정하고 마지막에 M과 S를 비교하면 풀린다.

• 시간복잡도 : O( N )
• 공간복잡도 : O( 1 )

 

B. 모험의 시작 ( UPSOLVING ) Silver Ⅳ

문제 바로가기 (클릭시 이동)

시간 제한 1초 / 메모리 제한 1024 MB

 

부산대학교 정보컴퓨터공학부는 매년 봄 MT를 떠난다. 봄 MT에 간 산지니는 아파트라는 술게임을 배웠다.

1. 게임을 시작한 사람이 아파트의 층수 𝑁을 정한다.
2. 게임의 모든 참가자는 자신의 두 손을 다른 사람과 겹치지 않는 높이로 뻗어 모든 참가자의 두 손이 서로 쌓이도록 한다.
3. 가장 아래에 있는 손을 빼 쌓여있는 손 가장 위에 쌓는다.
4. 3.의 과정을 𝑁번 반복한다. 𝑗번째로 쌓은 손이 𝑗층이 된다.
5.  𝑁층을 쌓는 참가자가 술을 마시고 게임이 종료된다.

새내기인 산지니는 누가 술을 마시게 될 지 궁금해졌다. 산지니를 위해 누가 술을 마시게 될 지 구해주자.

 

CODE - C++

#include <iostream>
#include <queue>
#include <vector>
#define MAX 10000
using namespace std;
int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    queue<short> Q;
    vector<short> V(MAX+1);
    short N,M;
    cin >> N >> M;
    for (short i=0;i<M;i++){
        short H1,H2;
        cin >> H1 >> H2;
        V[H1]=V[H2]=i+1;
    }
    for (short i=0;i<=MAX;i++){
        if (V[i]){
            Q.push(V[i]);
        }
    }
    while(--N){
        Q.push(Q.front());
        Q.pop();
    }
    cout << Q.front();
    return 0;
}

이 문제는 각자의 손이 초깃값으로 들어오고 손을 1개씩 올리면서 N번째에 손을 움직인 사람을 찾는 문제다.

나는 이 문제를 보고 손을 올린다는 소리가 들어오니까 큐를 떠올렸다.

그래서 큐에 손의 주인을 넣고 N번 돌려서 해결했다.

• 시간복잡도 : O( N + M )
• 공간복잡도 : O( MAX ) = O( 10000 )

 

C. 한빛미디어 (Easy) ( UPSOLVING ) Silver Ⅳ

문제 바로가기 (클릭시 이동)

시간 제한 1초 / 메모리 제한 1024 MB

 

이 문제는 "한빛미디어(Hard)" 문제와 입력 조건과 출력 조건이 다르다.

한빛미디어(주)는 '책으로 여는 IT 세상'을 만들어 갑니다. IT 세상의 주역은 '우리' 입니다. 한빛미디어(주)는 IT 세상의 주역들을 위한 프로그래밍, 컴퓨터공학, IT 에세이, Make, 리얼타임(전자책), OA, 그래픽, 나와 내 아이를 위한 실용 등 다양한 분야의 책으로 IT 세상을 만들어 가고 있습니다.

대학교를 졸업한 산지니는 2022년부터 부산대학교 프로그래밍 대회의 후원사를 맡아온 한빛미디어의 의뢰를 받았다. 바로 한빛미디어가 출판한 책들의 데이터베이스를 이용한 웹사이트의 책 진열 프로그램을 개발해달라는 의뢰였다. 산지니는 기쁜 마음으로 의뢰를 승낙했고, 프로그램을 개발하기 시작했다. 데이터베이스의 책들은 아래 규칙에 따라 웹사이트의 페이지에 진열된다.

• 웹사이트의 한 페이지에 책을 한 종류 이상 진열해야 한다.
• 가격이 두 배 이상 차이 나는 책을 한 페이지에 함께 진열할 수 없다. 예를 들어 가격이 3000원인 책은 5000원인 책과 함께 진열할 수 있지만 6000원인 책과는 함께 진열할 수 없다.

산지니는 책이 진열된 페이지가 많으면 고객이 책을 찾기 힘들 것으로 생각해 책이 진열될 페이지 수를 최소화하기로 했다. 산지니를 도와주자!

 

CODE - C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    vector<int> V;
    int N,M=0,K=0;
    cin >> N;
    while(N--){
        int S;
        cin >> S;
        V.push_back(S);
    }
    sort(V.begin(),V.end());
    while(!V.empty()){
        if (M*2>V.front()){
            V.erase(V.begin());
        }
        else {
            M=V.front();
            K++;
        }
    }
    cout << K;
    return 0;
}

이 문제는 N개의 책을 가격이 2배 이상 차이가 나지 않는 책끼리 묶는 문제다.

어차피 가격이 낮은 책은 1묶음으로 묶인다. 그러면 제일 가격이 낮은 책을 기준으로 최대한 뺀다면 효율적이다.

책을 정렬하고 기준 M을 잡아서 M*2보다 작다면 계속 erase하는 방식으로 풀었다.

• 시간복잡도 : O( N log N )
• 공간복잡도 : O( N )