[백준] 28303 자석 (+ 연속 구간의 최대 합) (python 파이썬)

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

28303번: 자석

---

N의 최댓값이 500,000이다. 시간제한은 2초나 되지만, N**2 같은 건 절대 안 된다.

이런 걸 고려해서 처음에는 DP, 그리디, 누적 합, 투포인터 등등 생각했었는데 1시간 정도 아이디어도 안 나왔다.

 

결국 알고리즘 분류를 확인했다. 누적 합 인걸 확인하고 최대한 누적 합 알고리즘을 적용하려고 했다.

코드 작성 중간에 내가 원하는 로직을 구현하기 위해 인터넷 검색도 사용했다.

 

실제 테스트 환경이었다면 못 풀었을 거 같다.  

하지만 경험을 쌓으면 충분히 해결할만한 문제 난이도라고 생각한다. 긍정적인 느낌을 받았다.

 

1. 문제를 해결할 때 사용하는 알고리즘의 대한 확신 (경험)

2. 중간중간 원하는 로직을 구현할 능력 (경험)

---

아이디어

이것저것 적어보면서 규칙 찾아보려고 했다.

f(1, 2) + f(2, 3) = f(1, 3) 같은 느낌의 규칙을 발견하고 수식으로 써봤다.

NS 방향을 고정한다는 전제하에 구간 a, b에 대해서 배터리의 에너지 변화값을 구하는 함수 f는 다음과 같다.

 

f(a, b) = A(a) - A(b) - (b - a) * K // (A(i)는 i번칸 에너지 상수, a, b는 번호 | a < b)

 

여기 f라는 함수는 다음과 같은 조건을 만족한다.

 

f(a, b) + f(b, c)

= A(a) - A(b) - (b - a) * K + A(b) - A(c) - (c - a) * K

= A(a) - A(c) - (a - c) * K

= f(a, c) //(a < b < c)

 

∴ f(a, b) + f(b, c) = f(a, c)

 

위와 같은 함수의 특징을 뜻하는 용어를 이산수학 같은 학교 수업에 배운 거 같은데 잘 기억이 나질 않는다. 혹시 아는 분은 알려주시면 감사하겠습니다.

 

f의 성질을 이용해 번호 차이가 1인걸 기준으로 배열을 작성한다. 예) [f(1,2), f(2,3), f(3,4), f(4,5)]

이 배열을 이용하면 자석 방향이 NS일 때의 모든 에너지 변화값을 구할 수 있다.

우리는 최댓값을 구할 거니까 이 배열의 연속 구간의 최대 합을 구해주면 된다.

 

SN방향도 위의 방법으로 구하면 된다. 최종적으로 NS의 최댓값, SN의 최댓값을 비교해서 출력하면 된다.

---

전체 코드

N, K = map(int, input().split())

tables = [int(x) for x in input().split()]

arr_NS = []
arr_SN = []

for i in range(1, N): # N-S
    arr_NS.append(tables[i - 1] - tables[i] - K)

for i in range(1, N): # S-N
    arr_SN.append(tables[i] - tables[i - 1] - K)

temp_NS = [0] * (N - 1)
temp_NS[0] = arr_NS[0]
for i in range(1, N - 1):
    temp_NS[i] = max(0, temp_NS[i - 1]) + arr_NS[i]

temp_SN = [0] * (N - 1)
temp_SN[0] = arr_SN[0]
for i in range(1, N - 1):
    temp_SN[i] = max(0, temp_SN[i - 1]) + arr_SN[i]

print(max((max(temp_NS),max(temp_SN))))

---

코드 설명

for i in range(1, N): # N-S
    arr_NS.append(tables[i - 1] - tables[i] - K)

arr_NS는 방향은 NS(N이 왼쪽), 위에서 말한 번호 차가 1일 때, 즉 자석의 길이가 2일 때 에너지 변화값들이다. 

 

temp_NS = [0] * (N - 1)
temp_NS[0] = arr_NS[0]
for i in range(1, N - 1):
    temp_NS[i] = max(0, temp_NS[i - 1]) + arr_NS[i]

배열의 연속 구간의 최대 합을 구하는 코드다. 동적 계획법(dp)으로 구현했다. 시간복잡도는 O(n)이다.

앞에서부터 쭉 더하다가 합이 음수가 나오면 앞의 부분을 버리는 방식이다. 

 

print(max((max(temp_NS),max(temp_SN))))

SN도 같은 방법으로 구해주고, 최댓값을 출력하면 된다.