[BOJ 2237] 수열 축소

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

2237번: 수열 축소

 

- 문제 요약

 

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}

 

 

- 알고리즘 정리

 

축소 연산을 진행할 때, arr[1]-arr[2]에 arr[3]~arr[n]을 더하거나(어떤 수에서 음수를 빼는 경우) 빼서 나오는 수를 미리 만들어서 사용할 수 있습니다. (DP)

DP 배열을 순회하면서 각 묶음의 플러스 개수에 따라 i=1 or i=2에 대해 축소연산을 진행해 줍니다.

 

 

- 코드 작성

 

#include<bits/stdc++.h>
using namespace std;

#define MAX 101
int n,t,arr[MAX],brr[MAX],dp[MAX][20001];

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n>>t;
	for(int i=1;i<=n;i++){
		cin>>arr[i];
	}	
	dp[2][arr[1]-arr[2]+10000]=1;
    for(int i=3;i<=n;i++){
    	for(int j=0;j<20001;j++){
    		if(dp[i-1][j]){
    			dp[i][j-arr[i]]=1;
    			dp[i][j+arr[i]]=2;
			}
		}
	}
	for(int i=n,p=t+10000;i>1;i--){
		brr[i]=dp[i][p];
		p=brr[i]-1?p-arr[i]:p+arr[i];
	}
    for(int i=3;i<=n;i++){
    	cout<<brr[i]<<'\n';
	}
	cout<<1;
}

코드 제출 결과