문제
Q개의 부품 A, W개의 부품 B, E개의 부품 C가 있다. 각 검사는 세 부품(a, b, c)을 하나씩 골라 함께 테스트하며, 결과는 합격(1) 또는 불합격(0)이다.
합격 검사에서 사용된 세 부품은 모두 양품이다. 불합격 검사에서는 세 부품 중 정확히 한 개가 불량품인데, 나머지 두 부품이 양품으로 확인된 경우 불량품을 특정할 수 있다. 각 부품 번호에 대해 양품(1), 불량품(0), 판단 불가(2)를 출력한다.
입력
첫째 줄에 Q, W, E, N이 주어진다. 이후 N개의 줄에 검사 결과 a b c res가 주어진다. res가 1이면 합격, 0이면 불합격이다.
출력
부품 번호 1부터 Q+W+E까지 각각 결과(0, 1, 2)를 한 줄씩 출력한다.
예제
| 입력 | 출력 |
|---|---|
1 1 1 2 1 2 3 1 1 2 3 0 | 1 1 1 |
풀이
합격/불합격 검사 결과를 분리하여 처리하는 두 단계 접근법을 사용한다.
- 입력을 받으면서 합격(res=1)인 검사의 세 부품을 모두 양품(
dt[x]=1,result[x]=1)으로 표시한다. 불합격 검사는vector에 따로 보관한다. - 모든 입력 처리 후, 불합격 검사 목록을 순회한다.
- 불합격 검사의 세 부품 중 두 부품이 양품(
dt=1)이고 나머지 한 부품의 상태가 확인되지 않은 경우, 그 부품을 불량품(result=0)으로 확정한다. - 양품도 불량품도 확정되지 않은 부품은 초기값 2(판단 불가)를 유지한다.
핵심 아이디어: 합격 검사 결과를 먼저 처리해 양품 정보를 최대한 확보한 뒤, 불합격 검사에서 "두 부품이 양품이면 나머지 한 부품이 불량품"이라는 조건으로 불량품을 추론한다.
코드
#include <iostream>
#include <vector>
#include <tuple>
using namespace std;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n, dt[301] = {
0,
},
q, w, e;
cin >> q >> w >> e >> n;
vector<tuple<int, int, int>> v;
vector<int> result(q + w + e + 1, 2);
for (int i = 0; i < n; i++)
{
int a, b, c, res;
cin >> a >> b >> c >> res;
if (res == 1)
{
dt[a] = 1, dt[b] = 1, dt[c] = 1;
result[a] = 1, result[b] = 1, result[c] = 1;
}
else
{
v.emplace_back(a, b, c);
}
}
for (int i = 0; i < v.size(); i++)
{
int a = get<0>(v[i]), b = get<1>(v[i]), c = get<2>(v[i]);
if (dt[a] == 1 && dt[c] == 1 && dt[b] != 1)
{
result[b] = 0;
}
else if (dt[a] != 1 && dt[c] == 1 && dt[b] == 1)
{
result[a] = 0;
}
else if (dt[a] == 1 && dt[c] != 1 && dt[b] == 1)
{
result[c] = 0;
}
}
for (int i = 1; i < result.size(); i++)
cout << result[i] << '\n';
return 0;
}복잡도
- 시간: O(N) — 합격 검사 처리 O(N) + 불합격 검사 처리 O(N)
- 공간: O(Q+W+E) — 부품 결과 배열 크기