백준 5557 c++ "1학년" -PlusUltraCode-

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

 

[필자 사고]

이 문제는 배낭 문제와 유사하다.

바깥 반복문에는 몇번째 숫자들의 경우의수로 반복문을 설계하고

안쪽 반복문에는 0~20까지의 숫자들의 모든 경우의 수를 구해줘야 된다.

 

필자는 dp 배열식을 dp[i][k] 라고 설정할 때 

i번째 수에서 k라는 값의 경우의 수를 dp라고 설정했다.

 

이 문제만의 매력은 0~20이라는 범위를 줘서 배낭문제 알고리즘을 이용하여 풀라는 힌트를 주었고

특정 어떤 값은 이전 i번째 값의 갯수를 기존값에 더하는 형태로 갱신해주는 경우이다.

 

필자는 이 부분에서 갱신 작업을 틀렸다. 덧셈이 2번일어나면 2를 곱한것과 같다..

 

아래는 상세한 코드 해설이다.

[코드 해설]

1. 입력 처리 (Input 함수)

Input() 함수는 문제에서 필요한 데이터를 입력받고 초기화하는 역할을 합니다.

• N (주어진 숫자의 개수)을 입력받습니다.
• dp 벡터를 (N+1) x 21 크기로 초기화합니다.
  • dp[i][k]는 i번째 숫자까지 연산했을 때 결과가 k가 되는 경우의 수를 저장하는 2차원 벡터입니다.
  • 숫자의 범위가 0~20이므로 dp[i][k]의 최대 인덱스는 20입니다.
• num 벡터를 입력받아, 주어진 숫자들을 저장합니다.

2. 동적 계획법을 이용한 특정 값 만들기 (Game_Start 함수)

이 함수는 DP(동적 계획법, Dynamic Programming) 를 이용하여 가능한 연산 결과의 경우의 수를 누적하는 방식으로 문제를 해결합니다.

초기값 설정

• dp[1][num[1]] = 1
  • 첫 번째 숫자는 그대로 사용해야 하므로, 첫 번째 숫자를 만들 수 있는 경우의 수를 1로 설정합니다.

DP 테이블 채우기

• i 번째 숫자까지 고려할 때, 이전 숫자의 계산 결과 (k)를 기준으로 연산을 수행합니다.
• k + num[i] 또는 k - num[i] 연산이 가능하면, 해당 결과를 dp[i][k]에 누적합니다.
• dp[i-1][k]가 0이 아니라면, 즉 이전 단계에서 k 값을 만들 수 있었다면, 현재 숫자를 더하거나 빼는 연산을 수행하여 다음 단계로 이동합니다.

최종 결과 출력

• dp[N-1][num[N]] 값을 출력합니다.
  • 마지막 숫자를 목표값으로 만들 수 있는 경우의 수를 출력합니다.

[소스 코드]

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

int N;
vector<vector<long>> dp;
vector<int> num;
void Input() {
	cin >> N;
	dp.resize(N + 1);
	num.resize(N + 1);
	for (int i = 0; i <= N; i++) {
		dp[i].resize(21);
	}

	for (int i = 1; i <= N; i++) {
		cin >> num[i];
	}
}

void Game_Start() {
	dp[1][num[1]] = 1;

	for (int i = 2; i < N; i++) {
		for (int k = 0; k <= 20; k++) {
			if (dp[i - 1][k]) {
				if (k + num[i] <= 20) {
					dp[i][k+num[i]] += dp[i - 1][k];
				}
				if (k - num[i] >= 0) {
					dp[i][k-num[i]] += dp[i - 1][k];
				}
			}
		}
	}
	cout << dp[N-1][num[N]];
}

int main(void) {
	Input();
	Game_Start();
}