방 청소

백준 9938번: 방 청소

아이디어

서랍끼리 union 연산을 수행한다. 이 때 루트에는 연결된 서랍들중에 빈자리가 몇개인지 음수로 표시한다.
이렇게 하면 술병을 입력받을 때마다 이 술을 보관할 수 있는지, 아니면 마셔야 하는지 알 수 있다.
보관할 수 있다면 (입력받은 서랍 두개의 루트를 참조하여 남은 자리가 있는지 확인) 서랍 두개를 union하고 루트에 한자리가 채워졌다고 표시해준다.

코드

#include <bits/stdc++.h>

using namespace std;

int N, L;
int p[300001];

int find(int n) {
    if (p[n] <= 0) return n;
    return p[n] = find(p[n]);
}

void Union(int n1, int n2) {
    n1 = find(n1);
    n2 = find(n2);
    if (n1 == n2) return;
    else {
        p[n1] += p[n2];
        p[n2] = n1;
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> L;

    memset(p, -1, sizeof(p));

    int a, b;
    for (int i = 0; i < N; i++) {
        cin >> a >> b;
        if (-p[find(a)] - p[find(b)] > 0) {
            cout << "LADICA\n";
            Union(a, b);
            p[find(a)]++;
        }
        else {
            cout << "SMECE\n";
        }
    }

    return 0;
}

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

p = [-1]*300001

def find(n):
    if p[n] <= 0:
        return n
    p[n] = find(p[n])
    return p[n]

def union(n1, n2):
    n1 = find(n1)
    n2 = find(n2)
    if n1 == n2:
        return
    p[n1] += p[n2]
    p[n2] = n1

N, L = map(int, input().split())

for _ in range(N):
    a, b = map(int, input().split())
    if p[find(a)] + p[find(b)] < 0:
        print("LADICA")
        union(a, b)
        p[find(a)] += 1
    else:
        print("SMECE")

여담

배열 p 한칸 모자라게 선언해서 틀린 건 알겠는데 왜 그게 메모리 초과로 뜬건지는 아직도 모르겠다. 혹시나 해서 파이썬으로 똑같이 풀어서 냈는데 IndexError가 떠서 알아챘다. 한 칸 넘어가게 참조해서 재귀함수 계속 호출하다 스택이 터져버린게 아닐까 추정중.
아 그리고 이문제 수행시간 내가 3등임 ㅋㅅㅋ