USACO 2019 January Contest - Silver ★

USACO 연습방에서 연습중입니다.

Grass Planting

BOJ 17024번 | 맞은 사람: 168 | 소요 시간: 10분 | 태그: 트리

• 주어진 입력은 트리 구조이다.
• 직접 인접하거나 중간 노드 하나를 끼고 인접하는 경우는 서로 종류가 달라야 한다.
• 트리의 전체 형태가 중요할까?
• 어떤 노드 기준으로 얼마나 많은 노드로 둘러싸였는지에 따라 종류의 개수가 달라질 것이다. (이를 차수라고 한다.)
• \(\max_{x\in G}\{\deg(x)\}+1\)이 답이 된다.

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

int main() {
    int n; cin >> n;
    int deg[n+1] = {0,};
    for (int i = 1; i < n; ++i) {
        int a, b; cin >> a >> b;
        ++deg[a], ++deg[b];
    }
    cout << *max_element(deg+1,deg+n+1)+1;
}

Icy Perimeter

BOJ 17025번 | 맞은 사람: 188 | 소요 시간: 30분 | 태그: 그래프 탐색

• 격자 위에서의 그래프 탐색 유형이다.
• 최대 크기 컴포넌트의 크기와 둘레를 구해야 한다.
• flood-fill을 적용해서 쉽게 풀면 된다.
• 구현이 빡세다. 이런 유형은 코드를 외워두거나 Code Snippet으로 관리하자.

#include <bits/stdc++.h>
#define REP(i,a,b) for (auto i = (a); i <= (b); ++i)
using namespace std;

using ci = complex<int>;
const ci d4[] {{0,1},{1,0},{0,-1},{-1,0}};
#define R real()
#define C imag()
#define P(x) (x).R][(x).C
#define isIn(x) (1 <= (x).R && (x).R <= n && 1 <= (x).C && (x).C <= n)

const int N = 1003;
int n;
bool b[N][N], visited[N][N];
pair<int,int> ans;

pair<int,int> dfs(ci s) {
    if (not isIn(s) or visited[P(s)]) return {0,0};
    visited[P(s)] = true;
    int area = 1, round = 0, cnt = 0;
    for (ci d : d4) {
        ci u = s+d;
        if (not isIn(u) or !b[P(u)]) {++cnt; continue;}
        if (visited[P(u)]) continue;
        auto [a,r] = dfs(u);
        area += a, round += r;
    }
    return {area,round+cnt};
}

int main() {
    cin >> n;
    REP(i,1,n) REP(j,1,n) {
       char c; cin >> c;
        b[i][j] = (c == '#');
    }
    REP(i,1,n) REP(j,1,n) if (b[i][j]) {
        auto [a,r] = dfs({i,j});
        ans = max(ans,{a,-r});
    }
    cout << ans.first << ' ' << -ans.second;
}

Mountain View

BOJ 17026번 | 맞은 사람: 141 | 소요 시간: 20분 | 태그: 스위핑

• 산들을 겹쳐서 보고 있을 때, 알아볼 수 있는 산의 개수를 구해야 한다.
• 겹쳐서 보이지 않는다는 것은 더 높은 산의 직선 아래 갇혔다는 뜻이다.
• 높은 직선을 b를 통해 관리하면서 가불 여부를 따져주자.

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

#define F first
#define S second

int main() {
    int n; cin >> n;
    pair<int,int> c[n+1], b = {0,0};
    bool canSee[n+1] = {0,};
    for (int i = 1; i <= n; ++i)
        cin >> c[i].F >> c[i].S, canSee[i] = true;
    sort(c+1,c+n+1);
    for (int i = 1; i <= n; ++i) {
        if (b.S-c[i].S >= c[i].F-b.F) canSee[i] = false;
        else b = c[i];
    }
    b = {1e9+3,0};
    for (int i = n; i >= 1; --i) {
        if (b.S-c[i].S >= -c[i].F+b.F) canSee[i] = false;
        else b = c[i];
    }
    cout << accumulate(canSee+1,canSee+n+1,0);
}