백준 25562 - 차의 개수 [Python]

https://www.acmicpc.net/problem/25562

25562번: 차의 개수

---

풀이 과정

서로 다른 정수 N개의 모든 쌍의 차를 구할 때, 서로 다른 차의 개수의 최대값과 최소값을 구하는 문제이다.

 

모든 쌍의 개수는 NC2 = N(N-1) / 2 이고 NC2개의 모든 쌍의 차가 전부 다른 값을 가질 때 서로 다른 차의 개수가 최대가 될 것 같다. 이런 경우가 존재하는지 생각해보자.

 

특정 수의 배수로도 만들어보고, 소수들로만도 한번 해보고... 여러 숫자를 넣어가면서 규칙을 찾다보면 1, 2, 4, 8... 과 같은 등비수열에서 모든 쌍의 차가 다른 값을 가짐을 파악할 수 있다. 마침 문제에서 N도 최대 30으로 주었고, 2^30이 int의 최대값을 넘어가지 않으므로 2배씩 커지는 등비수열을 출력해주면 실례가 된다. 서로 다른 차의 개수의 최대값은 N(N-1) / 2, 실례는 공비를 2로 갖는 등비수열을 출력해주면 된다.

 

서로 다른 차의 개수가 최소가 되는 경우는 언제인가? 여러가지 수를 넣어보면서 규칙을 찾다 보면 1, 2, 3, 4... 나 2, 4, 6, 8... 과 같은 등차수열에서 서로 다른 차의 개수가 N-1개로 가장 적어보인다. 다른 숫자 쌍을 넣어봐도 N-1개 보다 줄어드는 경우는 나타나지 않는다. 따라서 서로 다른 차의 개수의 최소값은 N-1, 실례는 임의의 공차를 갖는 등차수열을 출력하면 문제가 풀릴 것 같다.

 

실제로 코드를 작성하니 문제가 해결되었다.

---

소스 코드

import sys

N = int(sys.stdin.readline())
print(N*(N-1) // 2)
number = 1
for _ in range(N):
    print(number, end=' ')
    number *= 2
print()
print(N-1)
number = 1
for _ in range(N):
    print(number, end=' ')
    number += 1