SFPC 2024 (문제 해설?)

강경 젓갈 축제 (0), (1), (2) - (BOJ 기준 실버 3~실버 1?)(자료 구조, 정렬)

이미지클릭

• (0) 번의 정답은 다음과 같음

print("4 narang 89.8")
print("2 arang 90.5")
print("1 danghak 91.0")
print("2 meodol 90.5")
print("5 geumdong 87.8")

• (1), (2)번의 공통 해설은 다음을 참조

이 문제 같은 경우에는 자료구조와 정렬을 활용하여서 풀이가 가능합니다. 

1. 사람들의 모든 점수를 합산한다.
2. 상위 하위 k 개의 숫자를 총합산에서 빼준다. (정렬활용하여서 상위 하위 k개의 숫자를 구해줌)
3. 이후에 퓨플 다음과 같이 튜플 형식을 만들어준다.

vector<tuple<double, string, int, int>> ans; //점수, 이름, 입력된 순서, 순위(순위는 일단 0으로 받아줌)​

4. 그런 다음 점수를 중심으로 한 번더 정렬을 해준다.
5. 0으로 초기화 해주었던 순위를 알맞게 채워준다.
6. 이후에 입력된 순서를 기준으로 정렬해 주고 나머지 부분을 출력해 준다.

정답 코드

#include<bits/stdc++.h>
using namespace std;

int n, m, k;
vector<tuple<double, string, int, int>> ans; //평균 점수, 이름, 입력된 순서, 순위로 입력!

int main() {
    ios::sync_with_stdio(0); 
    cin.tie(0);

    cin >> n >> m >> k;

    for (int i = 1; i <= n; i++) {
        string s;
        double sum = 0;
        vector<double> v;
        cin >> s;

        for (int j = 0; j < m; j++) {
            double x;
            cin >> x;
            v.push_back(x);
            sum += x;
        }

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

        int l = 0, r = m - 1;
        for (int j = 0; j < k; j++) { //상위, 하위 k개의 숫자를 총합에 빼줌!
            sum -= v[l] + v[r];
            l++;
            r--;
        }

        double avg = sum / (m - 2 * k);
        avg = round(avg * 10) / 10.0; //반올림 실수 조심!
        ans.push_back({avg, s, i, 0}); //순서대로 저장해주기!
    }

    sort(ans.rbegin(), ans.rend()); //점수에 따라 내림 차순으로 정렬!

    int rank = 1;
    for (int i = 0; i < ans.size(); i++) {
        if (i > 0 && get<0>(ans[i]) < get<0>(ans[i - 1])) { //순위 정래주기!
            rank = i + 1;
        }
        get<3>(ans[i]) = rank;
    }
    
    sort(ans.begin(), ans.end(), [](const auto &a, const auto &b) {
        return get<2>(a) < get<2>(b);
    }); //입력된 순서를 기준으로 오름차순으로 정렬해주기

    for (auto [avg, name, index, rank] : ans) {
        cout << rank << " " << name << " " << fixed << setprecision(1) << avg << "\n";
    } //소수점 1자리 까지 출력해주기!
}

부여 궁남지 연꽃 키우기 (0), (1) - (BOJ 기준 골드 5~골드 4?)(bfs, 구현)

이미지클릭

• (0) 번의 정답은 다음과 같고 연꽃을 1이라고 했을 때 다음과 같이 출력됨

//정답
15

//연꽃:1, 물:0
1 1 1 1 0 
1 1 1 0 1 
1 1 0 1 1 
0 1 1 1 0

• (1) 번의 해설은 다음을 참조

・모든 꽃은 다음날 동시에 번식한다.
・현재 꽃의 위치에서 인접한 곳이 비어 있으면, 그 위치들로 번식한다.
・번식하지 못한 연꽃은 사라진다.

다음의 세 가지 조건으로 인해서 결론적으로 bfs를 사용해야 한다는 것은 알 수 있습니다. 
하지만 어떻게 구현을 해야 하는지 생각하기 약간 어려웠던 것 같습니다.

설명 퀄이 별로 안 좋아서 코드랑 같이 보는 것을 추천합니다...

1. 연꽃의 위치를 알려주는 배열(d)과 visited라는 배열을 만들어준다.(visited 중요!)
2. bfs를 하기 위한 큐와 re라는 백터도 하나 만들어준다.
3. 기본적으로 큐의 크기만큼을 반복해 준다. (그러지 않으면 날짜를 구분할 수 없음!)

<중요>
4-1. (x1, y1)을 기준으로 하여서 동서남북의 네 점 중 하나라도 비어있다면 flag==false로 해준다. (flag==false로 해주는 것은 연꽃이 번식이 가능함을 표시해 줌!)
4-2. (4-1)의 단계가 참이고, 만약에 그 점이 방문 처리가 안되어 있다면 큐에 그 점을 넣어주고 방문처리 해준다.

5. flag가 true라면 주변에 번식을 할 수 없다는 의미이기 때문에 re배열에 넣어둔다. 그게 아니면 큐에 넣어준다.
6. re에 들어 있는 값들은 번식이 불가능하기에 d를 0으로 처리해 준다.
7. 큐에 들어 있던 값들은 d를 1로 바꾸어준다.
8. 최종적으로 보았을 때 큐의 크기가 연꽃의 개수이므로 크기를 출력해 준다.

정답 코드

#include<bits/stdc++.h>
using namespace std;

int h, w, x, y, n;
const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
int d[104][104]; //연꽃의 분포
int visited[104][104]; //연꽃의 동일한 위치가 여러번 큐에 들어가는 것을 방지

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> h >> w >> x >> y >> n;

    d[x][y] = 1;
    queue<pair<int, int>> q; //살아있는 연꽃
    q.push({x, y});

    for (int i = 1; i <= n; i++) {
        int size = q.size();
        vector<pair<int, int>> re; //죽은 연꽃
        fill(&visited[0][0], &visited[0][0] + 104 * 104, 0); 

        while (size--) {
            auto [x1, y1] = q.front(); q.pop();
            bool flag = true;

            for (int j = 0; j < 4; j++) {
                int xx = x1 + dx[j], yy = y1 + dy[j];

                if (xx >= 0 && xx < h && yy >= 0 && yy < w && d[xx][yy] == 0) {
                    flag = false;

                    if (!visited[xx][yy]) { //만약 연꽃이 큐에 없다면 넣어주고 방문처리
                        q.push({xx, yy});
                        visited[xx][yy] = 1;
                    }
                }
            }

            if (flag) {//만약 연꽃이 죽었으면 re에 넣어줌
                re.push_back({x1, y1}); 
            } else { //아니면 큐로
                q.push({x1, y1});
            }
        }

        for (auto j : re) { //현제위치에 있는 연꽃을 없애줌
            d[j.first][j.second] = 0; 
        }

        int size1 = q.size();
        for (int j = 0; j < size1; j++) { //현제 위치에 연꽃을 추가해줌
            auto [x2, y2] = q.front(); q.pop();
            d[x2][y2] = 1;
            q.push({x2, y2});
        }
    }

    cout << (int)q.size(); 
}​

입장 포도 수확하기 (0), (1) - (BOJ 기준 실버 2~골드 5?)(그리디, 우선순위 큐)

이미지클릭

• (0) 번의 정답은 다음과 같음

166

• (1) 번의 해설은 다음을 참조

우선순위 큐를 활용한다면 쉽게 문제를 해결할 수 있음

정답 코드

#include<bits/stdc++.h>
using namespace std;
int n,m,k;
priority_queue<int> pq;
int main(){
      ios::sync_with_stdio(0);cin.tie(0);
      cin>>n>>m>>k;
      for(int i=1;i<=n;i++){
            int x; cin>>x;
            pq.push(x);
      }
      
      int ans=0;
      while(!pq.empty()){
            int x=pq.top(); pq.pop();
            if(x-m>0) pq.push(x-m), ans+=m; //m보다 크다면 ans==m으로 해주고 x-m을 다시 큐에 넣어줌
            else ans+=x; // 아니면 현제 포도의 개수를 더해줌
            k-=1;
            if(k<=0) break; //k, 즉 상자의 개수가 0보다 작거나 같으면 종료
      }
      cout<<ans;
}​

천안 호두과자 (0), (1) - (BOJ 기준 브론즈 4 ~ 브론즈 3?)(사칙 연산)

이미지 클릭

• (0) 번의 정답은 다음과 같음

3300

• (1) 번의 해설은 다음을 참조

간단한 사칙 연산 

m을 가지고 있는 돈이라고 했을 때 모든 호두과자의 가격을 뺐을 때 0보다 크면 m을 출력, 아니면 -1 출력

#include<bits/stdc++.h>
using namespace std;
int n,m;
int main(){
      ios::sync_with_stdio(0); cin.tie(0);
      cin>>n>>m;
      for(int i=1;i<=n;i++){
            int x; cin>>x;
            m-=x;
            if(m<=0){ // 현제 남은 금액이 0보다 작거나 같으면 -1 출력
                  cout<<-1;
                  return 0;
            }
      }
      cout<<m;
}​

청양 고추 구기자 축제 (0), (1) - (BOJ 기준 브론즈 1~ 실버 5?)(구현, 누적합?)

이미지클릭

• (0) 번의 정답은 다음과 같음

27

• (1) 번의 해설은 다음을 참조

이 문제는 피보나치수열과 비슷한 형태로 동작을 하는 데 다른 점은 초기의 1,2번의 값을 지정해 주고, 두 번째로는 30보다 같거나 크다면 현제 가족에게 1kg만 지급한다는 부분만 제외해 주면 된다.

#include<bits/stdc++.h>
using namespace std;
int k, a;
int dp[600004];
int main(){
      ios::sync_with_stdio(0); cin.tie(0);
      cin>>k>>a;
      if(k<3){ //만약 가족의 번호가 3보다 작으면 a, 즉 초기 무게를 출력해줌
            cout<<a;
            return 0;
      }
      dp[1]=dp[2]=a; // 초기 1,2번 가족의 값을 지정
      for(int i=3;i<=k;i++){
            if(dp[i-1]+dp[i-2]>=30) dp[i]=1; //만약 이전 두 집의 고추의 무게의 합이 30보다 크거나 같으면 1kg만 획득
            else dp[i]=dp[i-1]+dp[i-2]; //아니면 계속 진행
      }
      cout<<dp[k];
}

 

 

 

질문이나 오류 지적은 언제든지 환영입니다!