[백준 10220번] Self Representing Seq

10220번: Self Representing Seq

---

이번 포스팅은 바킹독님의 포스팅을 참고하여 작성하였습니다.

 

목차

• 문제 접근
• 문제 풀이

 

 

문제 접근

이 문제는 $\small{N}$이 주어졌을 때, 길이가 $\small{N}$이고 아래의 조건을 만족하는 수열 $\small{A}$의 개수를 구하는 것이다. ($\small{1 \leq N \leq 100}$)

$\small{A_i}$ = 수열 $\small{A}$에서 $\small{i}$가 등장하는 횟수 ($\small{0 \leq i < N}$)

 

자명한 조건들

A[0] + A[1] + ... + A[N-1] = N

A[i]는 배열 A에서 i가 나타난 횟수이다.
즉, A[0] + A[1] + ... + A[N-1]은 배열 A에서 각 숫자들이 나타난 횟수의 합이므로 N이 되는 것이다.

 

A[1], A[2], ..., A[N-1]은 모두 2이하이다.

i의 범위가 [1, N-1]일 때 A[i]가 3이상이면, i가 3번 이상 나타난다는 것이다.
그렇다면, A[0]를 제외한 A[p], A[q]에 i를 할당해야 한다. 즉, A[p] = i, A[q] = i가 된다.
이렇게 되면 p가 i번, q가 i번 나오게끔 배열을 만들어야 하며, 이런 과정을 반복하다 보면 첫 번째 조건을 만족할 수 없다.
따라서, A[0]를 제외한 A[i]는 모두 2이하인 수여야 한다.
즉, A[1], A[2], ..., A[N-1] 가 가질 수 있는 값은 0, 1, 2 세가지 중에 하나인 것이다.

 

 

 

문제 풀이

A[0]가 i라면 0이 i번 나오는 것이고 0으로 할당된 원소들은 추가적인 조건이 붙지 않는다.

예를 들어, A[p]에 0을 할당하여 A[p]=0이 된다고 해도 p의 개수는 0개 이므로 p는 추가하지 않아도 된다.

즉, A[0]은 값이 커진다 해도 지속적인 조건이 추가로 붙지 않는다.

 

따라서, A[0]의 값을 기준으로 생각해보자.

 

Case1. A[0] = 0

A[0] = 0인 것부터 0의 개수가 1개인데 A[0] = 0이므로 이 자체가 말이 안 된다.

 

Case2. A[0] = 1

A[0] = 1이면 A[1], A[2], ..., A[N-1]의 합은 N-1이어야 하며, 이 중에 하나가 0이어야 한다.

A[1], A[2], ..., A[N-1] 중에 하나가 0이면, 나머지 N-2개의 합이 N-1이 되어야 한다.

즉, 나머지 N-2개 중에서 1개는 2, 나머지는 1이 돼야 이를 만족할 수 있다.

정리하면, A[0] = 1이며 A[1], A[2], ... A[N-1] 중에서 하나는 0, 하나는 2, 나머지는 1이 돼야 하는 것이다.

이를 만족하는 경우는 N=4인 경우의 (1, 2, 1, 0)이 유일하다.

 

Case2. A[0] = 2

A[0] = 2이면 A[1], A[2], ..., A[N-1]의 합은 N-2이어야 하며, 이 중에 두개가 0이어야 한다.

A[1], A[2], ..., A[N-1] 중에 두개가 0이면, 나머지 N-3개의 합이 N-3이 되어야 한다.

즉, 나머지 N-3개 중에서 1개는 2, 나머지는 1이 돼야 이를 만족할 수 있다.

정리하면, A[0] = 2이며 A[1], A[2], ..., A[N-1] 중에서 두개는0, 하나는 2, 나머지는 1이 돼야 하는 것이다.

이를 만족하는 경우는 N=4인 경우에 (2, 0, 2, 0), N=5인 경우에 (2, 1, 2, 0, 0)이 유일하다.

 

Case3. A[0] = k ≥ 3

A[0] = k이면 A[1], A[2], ..., A[N-1]의 합은 N-k이어야 하며, 이 중에 k는 0이어야 한다.

A[1], A[2], ..., A[N-1] 중에 k개가 0이면, 나머지 N-k-1개의 합이 N-k가 되어야 한다.

즉, 나머지 N-k-1개 중에서 1개는 2, 나머지(N-k-2개)는 1이 돼야 이를 만족할 수 있다.

정리하면, A[0] = k이며 A[1], A[2], ..., A[N-1] 중에서 k개는 0, 하나는 2, 나머지(N-k-2개)는 1이 돼야 하는 것이다.

 

이러한 조건을 조금 더 면밀히 살펴보면 아래와 같은 조건을 추가로 얻을 수 있다.

- 1의 개수가 N-k-2이므로 A[1] = N-k-2가 돼야 한다.

- 하나는 2이므로 A[2] = 1가 돼야 한다.

- A[0] = k이므로 A[k] = 1이 돼야 한다.

 

A[2]는 1이므로 A[1] = N-k-2 = 2가 돼야 하므로 이를 만족하는 k = N-4임을 알 수 있다.

즉, A[0] = N-4, A[1] = 2, A[2] = 1, A[N-4] = 1을 만족하는 경우면 되는 것이다.

이는 N이 7이상인 경우엔 항상 만족하므로 N이 7이상인 경우는 항상 만족하는 경우가 있는 것이다.

 

 

정리하면, N = 1, 2, 3, 6인 경우엔 0개, N = 4인 경우엔 2개, 나머지 경우엔 1개임을 수학적으로 알 수 있다.

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

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);	
		
	int t; cin >> t;
	while (t--) {
		int x; cin >> x;
		if (x==1 || x==2 || x==3 || x==6) cout << 0 << '\n';
		else if (x == 4) cout << 2 << '\n';
		else cout << 1 << '\n';
	}

	return 0;
}