백준 1학년 - (C++)

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

SW Expert Academy

 

문제설명

탐색문제일까 싶었지만 N이 100이면 최악의 경우가 2의 99승까지 가기 때문에 무조건 DP로 풀어야 한다고 생각했다.

 

근데 DP의 가장 큰 문제는 점화식을 찾기 어렵다는 것이다. 30분 정도 고민해 봤지만 역시 생각해내기 어려워 다른 사람 풀이를 참고하였다.

 

알고리즘

핵심 변수는 dp[N][21] 인데 'N번 째 일 때 값이 0이상 20이하 이다.'를 나타낸 것이다. 이해하기가 쉽지 않은데 이 그림을 보면 이해하기 쉬울 것이다.

 

아래와 같은 예제가 주어졌을 때

5

9 3 3 3 6

 

DP를 쉽게 이해할 수 있는 그림

이러한 경우의 수가 나타나게 되는데 마지막 값은 6이 되야하기 때문에 18,12,6,0 에서 6까지 온 경로의 수를 구해주면 되는 것이다.

그림이 알아보기 어렵겠지만 최선이다..

 

그렇다면 경로의 수가 위 그림과 같이 3가지가 나오게 된다. 이 그림을 이해했다면 점화식을 쉽게 유도 할 수 있다.

dp[index번째 수][지금까지 계산된 수 - or + 새로운 수] += dp[index-1번 째 수][지금까지 계산된 수];

를 얻을 수 있을 것이다. 

 

주의사항

dp 사이즈를 생각해서 long long으로 선언해야 한다.

 

구현

#define _CRT_SECURE_NO_WARNINGS 
#include<cstdio>
#include<iostream>
#include<string.h>
#include<vector>
#include <climits>
#include<string>
#include<queue>

using namespace std;


int N;
int arr[101];
long long dp[101][21];


void solve() {
	dp[0][arr[0]] = 1;
	for (int i = 1; i < N-1; i++)
	{
		for (int j = 0; j < 21; j++)
		{
			if (dp[i - 1][j] > 0)
			{
				if (j+arr[i] < 21) dp[i][j+arr[i]] += dp[i - 1][j];
				if (j-arr[i] > -1) dp[i][j-arr[i]] += dp[i - 1][j];
;			}
		}
	}
	
}

int main()
{
	scanf("%d", &N);
	for (int i = 0; i < N; i++)
	{
		scanf("%d", &arr[i]);
	}

	solve();
	cout << dp[N - 2][arr[N - 1]];
	
}

 

참조

https://everenew.tistory.com/34