Hello 2022 A부터 B까지 업솔빙

Hello 2022 A부터 B까지 업솔빙

확률과 통계를 못하는 나는 경우의 수를 나누는 것을 정말 못한다. B번 문제가 그냥 경우의 수 나누는 문제 그자체라서 못풀겠다. 내가 하는 지금 문제풀이가 나중에 코딩테스트에 도움이 되길.

A. Stable Arrangement of Rooks (*800)

접기/펼치기

문제 설명
$n \times n$ 크기 체스보드와 $k$개 룩이 있다. 칸 $(x, y)$ 는 행 $x$와 열 $y$의 교차점이다.

만약 한 룩이 다른 모든 룩에게 잡히지 않는다면 이 배치는 좋다 고 한다.

만약 한 룩을 다른 인접한 칸에 한칸 옮겨서 좋지 않은 배치가 된다면 이 좋은 배치는 안정적이지 않다고 한다. 그렇지 않으면 이 배치는 안정적인 배치라고 한다.

$n \times n$ 크기의 판에 $k$개 룩을 안정적으로 배치하는 아무 방법이나 찾아라. 그렇지 않으면 -1을 출력하라.

문제 해설
각 룩을 인접한 한칸 이동했을 때 십자가로 되어 있는 모든 칸에 룩이 있으면 안된다. 또한 현재 위치한 룩에서 십자가로 되어 있는 모든 칸에 또한 룩이 있으면 안된다. 그렇기 때문에 맨 처음 룩을 $(1, 1)$ 에 두고 다음 룩을 $(3, 3)$, 그 다음 룩을 $(5, 5)$이렇게 놓으면 답이다. 그리고 체스판 크기보다 룩의 개수가 많으면 $-1$을 출력하면 된다.

정답 코드

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

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while(t--){
        int n, k; cin >> n >> k;
        if((n + 1) / 2 < k){
            cout << -1 << "\n";
            continue;
        }

        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(i == j and i % 2 == 0 and k > 0){
                    cout << "R";
                    k--;
                }
                else cout << ".";
            }
            cout << "\n";
        }
    }
    return 0;
}

B. Integers Shop (*1500)

접기/펼치기

문제 설명
정수 상점은 $n$개 조각으로 이루어져 있다. $i$번째 조각은 $l_i$ 부터 $r_i$까지에 있는 모든 정수를 포함하며 비용은 $c_i$원이다.

내일 상점에가서 조각을 살 예정인데, 최소 1개 이상의 조각을 살 것이다. 최종 비용은 모든 조각의 비용 합이다.

쇼핑을 하고 나서 선물로 정수 몇개를 더 받는다. 다음 조건을 모두 만족하는 정수 $x$를 모두 선물로 받는다.

• $x$를 사지 않았다.
• $x$보다 작은 정수 $l$을 구매했다.
• $x$보다 큰 정수 $r$을 구매했다.

기술적 문제로 인해서 오직 첫번째부터 $s$번째 조각까지만 살 수 있고 나머지 조각은 내일 살 수 있다.

진수는 가능한 많은 정수를 받고 싶다. 만약 다른 방법이 존재한다면 비용이 가장 작은 방법을 선택한다.

$1$부터 $n$까지 각 $s$중에서 오직 $s$번째까지 조각만 살 수 있는 진수가 내야하는 비용은 얼마일까?

문제 해설
그냥 경우의 수 나는 문제였다. 문제를 보면 가장 작은 수와 가장 큰 수, 그리고 가장 긴 조각 수만 유지하면 된다는 것을 알아야 한다. 왜냐하면 가장 작은 수와 가장 큰 수를 결정하면 나머지 숫자들은 모두 선물로 받기 때문에 의미가 없기 때문이다.

그렇기 때문에 조각이 들어 왔을때, 가장 작은 수를 가지고 있는 조각과 그 비용, 가장 큰 수를 가지고 있는 조각과 그 비용, 가장 긴 조각과 그 비용을 계속 최신화 해주고 다음 조건에 맞춰서 답을 출력한다.

1. 만약 가장 긴 조각의 거리와 가장 큰수와 가장 작은 수 사이의 거리가 서로 같은데, 비용이 가장 긴 조각이 더 작다면 그 값을 출력한다.
2. 그렇지 않으면 가장 큰수를 가진 조각의 비용 + 가장 작은수를 가진 조각의 비용의 합을 구한다.

정답 코드

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

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while(t--){
        int n; cin >> n;
        int a[n][3];
        for(int i = 0; i < n; i++) cin >> a[i][0] >> a[i][1] >> a[i][2];

        int l = 0, r = 0, len = 0;
        for(int i = 0; i < n; i++){
            if(a[i][0] < a[l][0] or (a[i][0] == a[l][0] and a[i][2] < a[l][2])) l = i;
            if(a[r][1] < a[i][1] or (a[r][1] == a[i][1] and a[i][2] < a[r][2])) r = i;
            if(a[len][1] - a[len][0] < a[i][1] - a[i][0] or 
            (a[len][1] - a[len][0] == a[i][1] - a[i][0] and a[i][2] < a[len][2])) len = i;

            if(a[len][1] - a[len][0] == a[r][1] - a[l][0] and a[r][2] + a[l][2] > a[len][2]) cout << a[len][2] << "\n";
            else cout << a[l][2] + a[r][2] << "\n";
        }
    }
    return 0;
}