[CodeUp/2822] 무한히 많은 연산 (Python)

Problem : 무한히 많은 연산 (codeup.kr)

Status : Solved

Time : 00:09:37

 

---

 

문제 설명

 

n개의 정수 ai와 정수 k가 주어진다.

n개의 정수 ai를 이용하여 아래와 같은 연산을 k번의 수행한다.

1. n개의 정수 중 가장 큰 값을 선택한다.
2. n개의 정수 ai를 (최댓값 - ai)로 바꾼다.


k번 연산 이후 n개의 정수 ai를 출력하시오.

 

입력 및 출력

 

입력

첫번째 줄에는 두개의 정수 n(1≤n≤10^5)과 k(1≤k≤10^18)가 공백을 기준으로 입력된다.
두번재 줄에는 n개의 정수 ai (−10^9≤ai≤10^9)가 공백을 기준으로 입력된다.

 

출력

k번 연산 결과 n개의 ai를 공백을 기준으로 출력한다.

 

입력 예시

2 1

-100 100

 

출력 예시

200 0

 

---

 

풀이

 

우선 생각해 볼 수 있는 방법은 brute force일 것이다. 따라서 그 코드는 다음이 된다 :

n, k = map(int, input().split())
a_lst = list(map(int, input().split()))

for _ in range(k) :
  a_max = max(a_lst)
  a_lst = [a_max - x for x in a_lst]

print(*a_lst)

 

당연히 틀렸다. 반복횟수 k는 최대 10^18까지 될 수 있으므로, 시간 초과가 난다. 따라서 규칙성을 생각해보아야 한다.

ai번째를 우선 한 번 연산을 수행하게 되면, i번째 원소는 다음과 같아진다 :

$$ a_i' = a_{max} - a_i $$

이 상황에서, 이 a개의 배열의 최댓값은 원래 값이 최소였던 경우, 즉 다음과 같다.

$$ a_{max}' = a_{max} - a_{min} $$

 

따라서 그 다음 연산을 수행할 때, i번째 원소는 다음과 같아진다 :

$$ a_i'' = a_{max}' - a_i' = (a_{max} - a_{min}) - (a_{max} - a_i) = a_i - a_{min} $$

이 때 최댓값은 자명하게도 원래 최댓값을 대입했을 때이다. 마지막으로, 이 연산을 다시 한 번 수행하면..

$$ a_i''' =  a_{max}'' - a_i'' = (a_{max} - a_{min}) - (a_i - a_{min}) = a_{max} - a_i = a_i' $$

즉 이 연산은 2를 주기로 반복된다. 위 식에 맞춰 구현하면 문제 풀이 완료.

 

 

풀이 코드 

n, k = map(int, input().split())
a_lst = list(map(int, input().split()))
a_min, a_max = min(a_lst), max(a_lst)
if k % 2 != 0 :
  print(*[ a_max - x for x in a_lst])
else :
  print(*[ x - a_min for x in a_lst])

 

풀이 완료!