[C++] 백준(BOJ) - 5557 : 1학년

28 Apr 2024 in Develop on C++, Algorithm

인프런에 있는 큰돌님의 강의 10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트를 듣고 정리한 필기입니다.

• 문제
• 입력
• 출력
• 알고리즘
• 풀이
• 코드
• 평가

문제

BOJ - 5557 : 1학년(링크)

상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 ‘=’을 넣고, 나머지 숫자 사이에는 ‘+’ 또는 ‘-‘를 넣어 등식을 만들며 놀고 있다. 예를 들어, “8 3 2 4 8 7 2 4 0 8 8”에서 등식 “8+3-2-4+8-7-2-4-0+8=8”을 만들 수 있다.

상근이는 올바른 등식을 만들려고 한다. 상근이는 아직 학교에서 음수를 배우지 않았고, 20을 넘는 수는 모른다. 따라서, 왼쪽부터 계산할 때, 중간에 나오는 수가 모두 0 이상 20 이하이어야 한다. 예를 들어, “8+3+2-4-8-7+2+4+0+8=8”은 올바른 등식이지만, 8+3+2-4-8-7이 음수이기 때문에, 상근이가 만들 수 없는 등식이다.

숫자가 주어졌을 때, 상근이가 만들 수 있는 올바른 등식의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 숫자의 개수 N이 주어진다. (3 ≤ N ≤ 100) 둘째 줄에는 0 이상 9 이하의 정수 N개가 공백으로 구분해 주어진다.

출력

첫째 줄에 상근이가 만들 수 있는 올바른 등식의 개수를 출력한다. 이 값은 $2^{63}-1$ 이하이다.

알고리즘

1. DP

풀이

• DP의 4가지 풀이법으로 차근차근 처리
• 경우의 수는 더하기
• int 형의 범위 $2^{31} - 1$ / long long 형의 범위 $2^{63} - 1$

코드

// BOJ - 5557 : 1학년
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n, a[105];
ll dp[105][21];

ll go(int idx, int sum)
{
	if (sum < 0 || sum > 20) return 0;
	ll& res = dp[idx][sum];
	if (res) return res;
	if (idx == n - 2) // (n-1)이 마지막 인덱스
	{
		if (sum == a[n - 1]) return 1;
		return 0;
	}
	res += go(idx + 1, sum + a[idx + 1]);
	res += go(idx + 1, sum - a[idx + 1]);
	return res;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n;

	for (int i = 0; i < n; i++) cin >> a[i];

	cout << go(0, a[0]) << '\n';

	return 0;
}

평가

• 기저사례, 메모이제이션, 메인로직, 초기화를 통해 DP 문제 TopDown 형식 풀이하기