[백준/5557] 1학년

1. 문제

1) 문제 링크

    : www.acmicpc.net/problem/5557

5557번: 1학년

 

2) 설명

숫자 배열이 있으면 마지막 숫자 전에 = 기호를, 나머지 각 숫자 사이에 +나 - 기호를 넣어서 등식을 성립하게 만들 수 있는 경우의 수를 구하면 된다.

단 계산 과정 중(왼쪽부터 계산하는 방식) 음수나 20을 초과하는 수가 나와서는 안 된다.

2. 풀이

1) 알고리즘

    : DP

 

2) 풀이 설명

 

0 ~ N-2 까지의 입력받은 숫자를 더하고 빼서 N-1번째에 입력받은 숫자를 만들어내면 된다.

즉 nums[0], nums[1], ... ,nums[N-2] 를 더하고 빼서 nums[N-1]을 만들면 된다.

 

그래서 i번째 이전 숫자들을 더하고 빼서 0부터 20까지 각각의 숫자를 만들 수 있는 경우의 수를 저장하는 DP 배열을 만들었다.

ex) DP[10][4] 에는 nums[0], nums[1], nums[2], nums[3], nums[4] 를 더하고 빼서 10을 만들 수 있는 경우의 수가 들어있다.

그러므로 DP배열은 21행( 0 ~ 20 ), N-1열( 0 ~ N-2 )을 가지게 된다.

초기값은 첫번째 DP[nums[0]][0] = 1로 주어진다.(첫 수(nums[0])으로 nums[0]을 만드는 경우의 수는 하나이기 때문에)

또한 점화식은 아래와 같이 세워진다.

 

DP[x][i] = DP[x][i] + DP[x-nums[i]] (단 x-nums[i] >= 0)

DP[x][i] = DP[x][i] + DP[x+nums[i]] (단 x+nums[i] <= 20)

 

이렇게 N-2열까지 돌리고나면 DP[nums[N-1]][N-2] 값이 답이 된다.(nums[0], nums[1], ... , nums[N-2]를 사용해서 nums[N-1]을 만드는 경우의 수)

 

3. 코드

/*
	1학년
	DP
*/
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	const int maxSum = 20;
	int N;
	cin >> N;

	vector<int> nums(N);

	for(int i=0;i<N;i++)
		cin >> nums[i];

	vector<vector<long long>> DP(21, vector<long long>(N, 0));
	
	DP[nums[0]][0] = 1;

	for(int i=1;i<N-1;i++){
		for(int j=0;j<=maxSum;j++){
			if(j-nums[i] >= 0)
				DP[j][i] += DP[j-nums[i]][i-1];
			if(j+nums[i] <= maxSum)
				DP[j][i] += DP[j+nums[i]][i-1];
		}
	}

	cout << DP[nums[N-1]][N-2] << "\n";

	return 0;
}

 

4. 느낀점

 

 - 값의 범위 잘 생각하기(long long 줘야하는데 int로 선언해서 틀렸었다.)

 - 가독성 높은 점화식 세우기