문제 바로가기
문제:
소 $N$마리가 정보섬에 올라왔다! 소들은 정보섬 1층 앞마당에서 A_1, A_2, A_3, \dots, A_N, A_1의 순서대로 동그랗게 앉아 쉬고 있다. 각 소들에게는 품질 점수 A_i가 적힌 스티커가 붙어 있다. 욱제는 소 떼 옆에서 효빈이가 계산해 둔 어떤 계산 식을 발견했는데, 그것은 아래와 같다. S = \sum_{i=1}^N(A_{i}×A_{i+1}×A_{i+2}×A_{i+3}) (단, A_{N+1}=A_{1}, A_{N+2}=A_{2}, A_{N+3}=A_{3}) 풀어 쓰자면, 원형으로 둘러 앉은 소들에 대해서, 연속한 네 마리 소들의 품질 점수를 곱한 값을 모두 더한 것이다. 욱제는 효빈이가 학교를 떠나지 못하도록 심술부릴 작정이다. 욱제는 총 Q번에 걸쳐 어떤 i번째 소를 선택할 것이다. 그러고는 A_i가 적힌 스티커를 떼어내고, A_i \times -1이 적힌 스티커를 붙일 작정이다. 그러면 효빈이는 Q번에 걸쳐서 S를 다시 계산해야 한다. 한 번 바꾼 스티커는 다음에 또 다시 바꾸지 않는 이상 계속 유지된다.
효빈이의 절친인 당신은 악동 욱제에게 괴롭힘 받는 효빈이를 도와 주기로 했다. 효빈이를 도와 S 를 계산해보자
입력:
첫째 줄에 소의 수를 나타내는 N과 욱제가 장난칠 횟수 Q가 주어진다. 둘째 줄에 N마리 소들의 품질 점수 A_i가 순서대로 주어진다. 셋째 줄에 욱제가 장난칠 Q개의 소의 번호 Q_i가 순서대로 주어진다.
출력:
Q개의 줄에 걸쳐 다시 계산된 S의 값을 출력한다.
풀이:
시간 초과 풀이:
import sys
from collections import deque
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')
n, q = map(int,input().split())
lst = deque(list(map(int, input().split())))
change_num = list(map(int,input().split()))
res = []
def calculate(lst):
res = []
for i in range(n):
temp = lst[0] * lst[1] * lst[2] * lst[3]
res.append(temp)
lst.rotate(-1)
return sum(res)
for i in range(q):
lst[change_num[i]-1] = lst[change_num[i]-1] * -1
temp_res = calculate(lst)
res.append(temp_res)
print(*res,sep="\n")
정답
import sys
from collections import deque
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')
n, q = map(int,input().split())
lst = deque(list(map(int, input().split())))
change_num = list(map(int,input().split()))
dp = [0] * n
# dp[0 -1 -2 -3]
for i in range(n):
dp[i] = lst[i%n] * lst[(i+1)%n] * lst[(i+2)%n] * lst[(i+3)%n]
result = sum(dp)
for num in change_num:
for j in range(num-3,num+1):
dp[(j-1)%n] *= -1
result += 2 * dp[(j-1)%n]
print(result)
숫자의 -1 을 곱하는 부분, 4개의 합을 구하는 부분을 바꿔주었다.
댓글