백준 #25562 차의 개수 (파이썬)

문제 바로가기

문제

 $1$ 이상 $10^9$ 이하의 서로 다른 정수 $N$개를 임의로 정하고 가능한 모든 쌍 $N(N-1)/2$개의 차를 구한다. 이때, 서로 다른 차의 개수의 최댓값과 최솟값을 구하고 각각 실례를 구성하여라.

입력

첫 번째 줄에 $N$이 주어진다. $(2 \leq N \leq 30)$ 

출력

첫 번째 줄에 서로 다른 차의 개수의 최댓값을 출력한다.

두 번째 줄에 서로 다른 차의 개수가 최댓값이 되도록 하는 $1$ 이상 $10^9$ 이하의 서로 다른 정수 $N$개를 공백으로 구분하여 출력한다.

세 번째 줄에 서로 다른 차의 개수의 최솟값을 출력한다.

네 번째 줄에 서로 다른 차의 개수가 최솟값이 되도록 하는 $1$ 이상 $10^9$ 이하의 서로 다른 정수 $N$개를 공백으로 구분하여 출력한다.

예제 입력

3

예제 출력

3
4 8 7
2
9 3 6

문제 이해하기

1. 스페셜 저지 배지가 붙었다는 것은 다양한 출력이 정답으로 인정될 수 있다는 것이다. 즉, 예제 출력과 나와 있는 것과 꼭 같지 않다고 하더라도 정답이 될 수 있다. 전략적 접근 가능
2. 서로 다른 차의 개수가 왜 N(N-1)/2가 되는 이유: 차를 구할 두 개의 숫자를 순서에 관계없이 구하는 것이므로, N(N-1)/2는 N combination 2로 해석할 수 있다.

문제 풀기

1. 첫 번째 출력 (서로 다른 차의 개수의 최댓값)
   • 전체 차의 개수는 N(N-1)/2이고, 모든 차가 다른 값을 가질 때 차의 개수가 최대가 됨
   • 정답은 N(N-1)/2
2. 두 번째 출력(서로 다른 차의 개수가 최댓값이 되도록 하는 정수 N개)
   • 이웃한 정수들의 차끼리 달라야 하는 것은 당연한 것임. 어차피 조건을 만족하는 하나의 수열만 찾으면 되므로, 편의를 위해 이웃한 정수들끼리의 차가 계속 증가한다고 가정
   • 하지만 만약 이웃한 정수들끼리의 차가 등차로 증가할 경우, 차의 값은 최대가 될 수 없다.
   • 예를 들어 만약 이웃 원소 간 차가 1씩 증가하는 수열(1, 2, 4, 7, 11 ...)에서 1과 4의 차는 4와 7의 차와 동일하기 때문이다.
   • 이는 이웃 원소 간 차로 이루어진 또다른 수열(1, 2, 3, 4...)을 생각해보았을 때, 이전 원소들의 합이 다음 원소가 될 수 있기 때문이다.
   • 따라서 차의 개수가 최대가 되기 위해서는, 이웃 원소 간 차로 이루어진 수열에서 이전 원소들의 합이 다음 원소가 될 수 없어야 한다.
   • 만약 차가 등비로 증가하면, 이전 원소들의 합은 2^n-1이 되기 때문에 그 다음 원소인 2^n이 될 수 없다.
   • 정답은 [2**i for i in range(N)] (2는 임의의 숫자로, 바뀌어도 무방함)
3. 세 번째 출력 (서로 다른 차의 개수의 최솟값)
   • 이웃한 원소들의 차가 모두 동일할 경우 차의 개수가 최소가 된다.
   • 이웃한 원소들의 차가 모두 동일하면 1번째 원소와 2번째 원소의 차, 1번째 원소와 3번째 원소의 차, ..., 1번째 원소와 n번째 원소의 차가 서로 다른 차의 전부가 되므로 차의 개수는 총 n-1이다.
   • 정답은 n-1
4. 네 번째 출력 (서로 다른 차의 개수가 최솟값이 되도록 하는 정수 N개)
   • 앞서 말한 것과 같이 이웃한 원소들의 차가 모두 동일할 때, 차의 개수는 최소가 된다.
   • 이 조건을 만족하는 수열은 등차수열
   • 정답은 [1 + i for i in range(N)]

총평

사실 2번째 출력 때문에 성공하지는 못한 문제. 수학개념을 가지고 많이 놀아봐야 풀 수 있는 문제같다.