제4회 숙명여자대학교 프로그래밍 경진대회 (SMUPC) - UPSOLVING

대회 날짜 : 2024년 5월 18일

 

A. SMUPC NAME ( UPSOLVING ) Bronze 1

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

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

알고리즘 분류 : 구현, 문자열

 

연재는 제4회 SMUPC에 출전하는 사람들을 위해 SMUPC NAME을 만들어주려고 한다. SMUPC NAME을 만드는 방법은 아래와 같다.

1. 출전자의 영어 이름에서 알파벳이 중복되지 않도록 추출한다. 특정 알파벳이 여러 번 등장한다면 처음 등장한 경우를 제외하고 해당 알파벳을 버린다.
2. 1번을 통해 만들어진 문자열 맨 뒤에 1번 과정에서 버려진 문자의 총개수에 4를 더한 값을 붙인다.
3. 2번을 통해 만들어진 문자열 맨 앞에 출전 등록 번호에 1906을 더한 값을 붙인다.
4. 3번을 통해 만들어진 문자열을 뒤집는다.
5. 4번을 통해 만들어진 문자열 맨 앞에 "smupc_"를 붙인다.

출전 등록 번호가 2이며 "yeonjaechoi" 라는 영어 이름을 가진 사람의 SMUPC NAME을 규칙에 따라 만들면 다음과 같다.

1. yeonjachi
2. yeonjachi6
3. 1908yeonjachi6
4. 6ihcajnoey8091
5. smupc_6ihcajnoey8091

출전 등록 번호와 영어 이름이 주어지면 그 사람의 SMUPC NAME을 출력하자.

 

CODE - C++

#include <iostream>
#include <algorithm>
using namespace std;
int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    string S;
    short N,M=4,i,j;
    cin >> N >> S;
    for (i=1;i<S.length();i++){
        for (j=0;j<i;j++){
            if (S[i]==S[j]){
                S.erase(S.begin()+i);
                ++M,--i;
                break;
            }
        }
    }
    S+=to_string(M);
    S.insert(0,to_string(N+1906));
    reverse(S.begin(),S.end());
    cout << "smupc_" << S;
    return 0;
}

이 문제는 정해진 방식으로 만들면 되는 문제다.

그냥 1, 2, 3, 4, 5에 따라서 코딩을 하면 돼서 따로 설명이 필요가 없을듯하다.

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

 

B. 열심히 일하는 중 ( UPSOLVING ) Silver 1

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

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

알고리즘 분류 : 구현, 자료 구조, 시뮬레이션, 우선순위 큐

 

송이는 이번 학기에 할 일이 매우 많다. 𝑁개의 일 중 어떤 일부터 해야 할지 고민하던 중 송이에게 좋은 아이디어가 떠올랐다! 바로 해야 할 일 각각의 중요도를 산정하고, 중요도가 높은 일부터 하는 것이다. 송이는 하루에 하나의 일만 처리할 수 있으며, 일을 처리한 후 그 일의 중요도는 𝑀만큼 감소한다. 일의 중요도가 𝐾 이하가 되면 그 일은 완료한 것으로 간주한다. 중요도를 일별로 산정하던 중 송이는 문득 일하면서 본인이 매일 느낄 만족감이 궁금해졌다. 오늘의 만족감은 전날의 만족감을 𝑌, 오늘 할 일의 중요도를 𝑃라 할 때 ⌊𝑌/2⌋+𝑃와 같다.

예를 들면 다음과 같다. 전날 송이의 만족도가 21이고, 송이가 오늘 할 일의 중요도가 10, 𝑀의 값이 4라고 가정했을 때 송이가 오늘 느낄 만족감은 ⌊212⌋+10 = 20이 된다. 이후 송이가 오늘 한 일의 중요도는 4만큼 감소해서 6이 된다.

송이가 해야 할 일의 개수 𝑁, 일을 처리했을 때 감소하는 중요도 𝑀, 완료한 것으로 간주하는 중요도의 최댓값 𝐾가 주어진 후, 𝑖번 일이 가지는 중요도 𝐷𝑖가 입력으로 𝑁개 주어진다. 송이가 모든 일을 끝낼 때까지 며칠이 걸리는지, 그리고 모든 일을 끝낼 때까지 송이가 일별로 느낀 만족감을 한 줄마다 출력하자. 단, 첫날의 경우 전날의 만족감을 0으로 간주한다.

 

CODE - C++

#include <iostream>
#include <queue>
using namespace std;
int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    priority_queue<short> D;
    queue<short> Q;
    int S=0;
    short N,M,K,d,P=0;
    cin >> N >> M >> K;
    while(N--){
        cin >> d;
        D.push(d);
    }
    while(D.top()>K){
        P=P/2+D.top(),++S;
        Q.push(P);
        D.push(D.top()-M);
        D.pop();
    }
    cout << S << "\n";
    while(!Q.empty()){
        cout << Q.front() << "\n";
        Q.pop();
    }
    return 0;
}

이 문제는 우선순위 큐를 활용해서 가장 큰 값을 M씩 빼서 K이하가 되도록 만드는 문제다.

while문으로 우선순위 큐 D의 큰 값이 K보다 클 때만 돌아가도록 만들어서 풀이가 간단하게 가능했다.

그리고 만족감을 저장하는 자료구조는 큐를 사용했는데 왜냐하면 굳이 vector가 필요 없어서 더 빠른 큐를 사용했다.

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