[백준 25378번] 조약돌 (Python3)

N = int(input())
rock = [*map(int,input().split())]
DP = [0]*N
for i in range(N):
  DP[i] = max(DP[i],DP[i-1])
  x = rock[i]
  for j in range(i+1,N):
    x = rock[j]-x
    if x<0:
      break
    if x==0:
      DP[j] = max(DP[j],DP[i-1]+1)
      break
print(N-DP[-1])

간단한 DP 문제

1번작업을 통해서 작업의 횟수를 줄이려면 무조건 현재위치에 남은 돌을 전부 가져가야한다는 사실만 파악하면 쉽게 해결할 수 있다.

 

풀이를 설명하면,

1. DP[i]는 i까지의 조약돌 중에서 1번과정을 통해 작업횟수를 몇 번 줄였는지의 최댓값이다.

2. 현재위치 i에서 i위치 돌의 개수 x만큼 전부 가져가고, i+1에서도 x만큼 가져간 후 남은 돌만큼을 i+2에서 가져가고.... 하면서 남은 돌이 0이 될때까지 1번과정을 실행해본다.

3. 2에서 남은 돌이 0이 되는 경우 0이된 좌표 j에서 DP[j]를 DP[i-1]+1로 갱신한다.

4. N-DP[N-1]을 출력한다.

 

이때 2번과정에서 남은 돌이 음수가 되면 탐색을 종료해야한다. 이걸 파악하지 못해서 틀렸습니다가 여러번 발생한 문제였다.

 

 

오늘의 교훈) 개수는 음수가 될 수 없다는걸 주의하자