백준 5557번 1학년

< 백준 5557번 1학년 - 마포 코딩박 >

사용한 알고리즘: DP


 N개의 수와 덧셈, 뺄셈 연산으로 만들 수 있는 올바른 등식수를 구하는 문제였습니다.
 마지막 수 앞에는 '=' 이 들어가야 합니다.

문제풀이는 다음과 같습니다.

(1) (코드 6~7)
 'dp[x][temp]: "x번째 도착, 이전 계산값이 temp인(x-1번째 까지 계산) 상태" 에서 만들 수 있는 올바른 등식 수' 로 dp 값을 설정해 주었습니다.

(2) (코드 8~28, 34~35)
 dp값을 계산해주는 함수를 만들어 줍니다.
 dp 설정에 따르면 dp[i][temp] = dp[i+1][temp+(i번째 값)] + dp[i+1][temp-(i번째 값)] 이겠죠.
 시작은 ( 2번째 도착, 이전계산값(=1번째 값)) 으로 하면 됩니다.

	#include <iostream>
	#include <cstring>
	using namespace std;
	int N, arr[101], want;
	//dp[x][temp]: x 번째 수 도착, 이전 계산값이 temp 인 상태에서 만들 수 있는 올바른 등식 수
	long long dp[101][1000];
	//index , 이전까지 계산값
	long long MakeAns(int idx, int temp){
	// 중간 계산값이 음수이거나, 20을 넘어가면 안된다
	if(temp<0||temp>20) return 0;
	// 마지막 숫자에 도착했을 떄
	if(idx==N){
	// 이전까지 계산값 = 마지막 숫자
	if(temp==arr[N]) return 1;
	// 아니면 등식성립 안함
	return 0;
	}
	long long &ret = dp[idx][temp];
	// 이미 탐색한 값이면 리턴
	if(ret!=-1) return ret;
	ret = 0LL;
	// 이전 index와 현재 index 사이 연산이 뺄셈인 경우
	ret += MakeAns(idx+1,temp-arr[idx]);
	// 이전 index와 현재 index 사이 연산이 덧셈인 경우
	ret += MakeAns(idx+1,temp+arr[idx]);
	return ret;
	}
	int main(){ios::sync_with_stdio(false);cout.tie(NULL);cin.tie(NULL);
	cin >> N;
	for(int i=1; i<=N; ++i) cin >> arr[i];
	memset(dp,-1,sizeof(dp));
	// 2번째꺼부터 보고, 이전 계산값은 1번째 수 이겠죠.
	cout << MakeAns(2,arr[1]) << '\n';
	return 0;
	}

view raw BOJ 5557.cpp hosted with ❤ by GitHub