BOJ 1813 - 논리학 교수 링크
(2023.05.17 기준 B1)

문제

"정확하게 i개의 말은 참이다" 라는 내용이 총 N개가 적혀 있다. i와 N은 50보다 작거나 같은 음이 아닌 정수일 때, 몇 개가 참인지 출력

알고리즘

애드혹. 문제를 잘 살펴보자.

풀이

첫번째 예제를 살펴보자.

• 0개의 말은 참이다. 라는 말은 불가능하다. 0개의 말이 참이면 이 말 자체가 참이 되기 때문.
• 1개의 말은 참이다. 라는 말은 가능하다. 0 2 3은 모순이고 1은 참이면 성립되기 때문.
• 2개의 말은 참이다. 라는 말은 불가능하다. 2가 참이고, 0 1은 참이면 불가능하며, 3이 참이면, 3을 채울 수가 없기 때문.
• 3개의 말은 참이다. 라는 말은 불가능하다. 2와 같은 경우가 생긴다.

결국, "정확하게 i개의 말은 참이다" 라는 내용이 i개가 있어야, 서로가 참이 되게끔 i개의 참을 정확하게 채워줄 수 있어서 참이 된다.

코드

• C++

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

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

    int N;
    cin >> N;

    // 참이 n개라는 말이 각각 몇개인지 센다.
    int ct[51]; fill(ct, ct + 51, 0);
    for (int i = 0, n; i < N; i++)
        cin >> n, ct[n]++;

    // 참이 n개다 라는 말이 n개와 같다면 이는 참이 된다.
    for (int i = 50; i >= 0; i--)
        if (ct[i] == i){
            cout << i;
            return 0;
        }

    // 참인 말을 찾지 못했다면 -1 출력
    cout << -1;
}

• Python

N, *lst = map(int, open(0).read().split())

# 참이 n개라는 말이 각각 몇개인지 센다.
ct = [0] * 51
for n in lst:
    ct[n] += 1

# 참이 n개다 라는 말이 n개와 같다면 이는 참이 된다.
for i in range(50, -1, -1):
    if ct[i] == i:
        print(i)
        break
else: # 참인 말을 찾지 못했다면 -1 출력
    print(-1)