[백준/2237] 수열 축소 (Python)

Problem : https://www.acmicpc.net/problem/2237

2237번: 수열 축소

 

Difficulty : Platinum 4

 

Status : Solved

 

Time : 00:37:50

 

---

 

문제 설명

 

 

N개의 양수로 이루어진 수열 {A[1], A[2], …, A[N]}이 있다. 이 수열에 A[i]에서 A[i+1]을 빼는 축소 연산을 적용하려 한다. 축소 연산은 CON이라는 함수로 나타낼 수 있으며, CON(A, i)를 수행하면 {A[1], A[2], …, A[i-1], A[i] - A[i+1], A[i+2], …, A[N]}의 수열을 얻는다.

이와 같은 축소 연산을 N-1번 적용하면, 수열의 길이가 N-1, N-2, …, 1이 되어 결국에는 한 수만 남게 된다. 이와 같은 축소 연산을 적용하여 T라는 수를 만들 수 있는지 알아보려 한다.

예를 들어 {12, 10, 4, 3, 5}라는 수열에 다음과 같은 축소 연산을 적용하면 4를 만들 수 있다.

 

• CON( {12, 10, 4, 3, 5}, 2 ) = {12, 6, 3, 5}
• CON( {12, 6, 3, 5}, 3 ) = {12, 6, -2}
• CON( {12, 6, -2}, 2 ) = {12, 8}
• CON( {12, 8}, 1 ) = {4}

 

입력 및 출력

 

입력

 

첫째 줄에 N(1 ≤ N ≤ 100), T(0 ≤ |T| ≤ 10,000)이 주어진다. 다음 줄에는 A[1], A[2], … A[N]이 주어진다. A[i]는 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.

 

출력

 

첫째 줄부터 사용한 순서대로 축소 연산에서의 i를 출력한다. 항상 가능한 경우만 입력으로 주어지며, 답이 여러 개 존재할 경우에는 임의의 하나를 출력하면 된다.

 

입력 예시

 

4 5
10 2 5 2

 

출력 예시

 

1
2
1

 

 

---

 

풀이

 

정답이 항상 존재하는 경우이므로 N <= 2인 경우를 먼저 제외하자.

 

이 문제를 조금 바꾸어 생각해보자. 예제의 12, 10, 4, 3, 5 인 경우는

 

12 - 10 + 4 + 3 - 5 = 12 - (10 - 4 - 3) - 5 = 4

 

로 바꾸어 줄 수 있다. 즉 본 수열을 a[1] - a[2] - a[3] - a[4] .. - a[N]의 식으로 바꾸고, 어디에 괄호를 씌울지를 결정하는 문제와 동일하다. 제약조건 상으로, a[2]의 경우 무조건 뺄셈밖에 성립하지 않는다.

 

앞선 식을 다시 보면, 3 <= i <= N인 모든 i에 대하여 i를 더할지, 뺄지를 결정하는 문제로도 볼 수 있다. 이 때 더해지는 i의 총합을 X, 그 나머지의 총합을 Y라 두면 다음 두 식이 성립한다. 

 

 

즉 우리가 구해야 할 X는 다음과 같다.

 

t, s는 결정된 상수이며, 이 문제는 3 <= i <= N인 수들을 조합하여 합이 X인 경우의 수를 찾는 문제로 변화했다. 즉 다이나믹 프로그래밍을 적용할 수 있다. 우리는 단 하나의 답만을 저장하면 되므로, 방문 여부와 더한 인덱스만을 참조하여 DP를 완성할 수 있다.

 

이렇게 완성한 DP는 위 식에서 더해주어야 할 수들의 인덱스를 저장하고 있다. 우리는 이 정보를 토대로 괄호를 삽입하면 된다.

• 만약 더해주지 않아도 된다면 CON(A, i)를 바로 호출 가능하다.
• 만약 3 <= i <= j <=  N 구간이 덧셈이라면, i구간의 뺄셈을 전부 처리하고 i-1구간의 뺄셈을 처리하면 된다. (괄호 연산의 결과에 의해 i구간의 뺄셈은 덧셈으로 변화한다).
• 또한 축소 연산의 처리를 고려할 때, 실질적으로 CON(A, i)를 (j-i)번 수행한 뒤 CON(A, i-1)을 수행하면 동일한 결과가 성립한다. 
• 뺄셈도 마찬가지이므로, i = 2으로 고정 가능하다. 즉 뺄셈일 경우 CON(A, 1)을 호출. 덧셈 구간이라면 CON(A, 2)를 (i-j)번 호출 후 CON(A, 1)을 호출하는 식으로 앞에서부터 처리 가능하다.

 

풀이 코드

N, T = map(int, input().split())
nums = list(map(int, input().split()))
if N == 1 :
  exit()
if N == 2 :
  print(1)
  exit()

t = T - nums[0] + nums[1]
s = sum(nums[2:])
target = (t + s) // 2
is_pos = [False]*N
dp = [[list() for _ in range(target+1)] for _ in range(N)]

for i in range(2, N) :
  if nums[i] > target :
    continue
  dp[i][nums[i]].append(i)
  
for i in range(2, N-1) :
  for j in range(target+1) :
    if not dp[i][j] :
      continue
    if not dp[i+1][j] :
      dp[i+1][j] += dp[i][j]
    if j + nums[i+1] <= target and not dp[i+1][j+nums[i+1]] :
      dp[i+1][j+nums[i+1]] += dp[i][j]
      dp[i+1][j+nums[i+1]].append(i+1)

for i in dp[-1][target] :
  is_pos[i] = True

cnt = 0 
for i in range(2, N) :
  if not is_pos[i] :
    while cnt :
      cnt -= 1
      print(2)
    print(1)
  else :
    cnt += 1
while cnt :
  cnt -= 1
  print(2)
print(1)

풀이 완료!