Suhwanc

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

 

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을 넘는 수는 모른다.

www.acmicpc.net

 

문제 설명

N개의 숫자가 주어졌을 때, N-1 개의 수 가운데에 + 또는 - 를 추가하여 n번 째 수를 만들 수 있는

등식의 개수를 출력하는 문제이다.

 

풀이

다이내믹 프로그래밍 문제입니다!

이 문제의 좋은 점은 중간에 나오는 수가 모두 0 이상 20 이하라는 조건이 있기 때문에

dp로 풀 수 있다는 것이다.

d[i][j] : 숫자 i번까지의 등식 결괏값이 j

로 설정해두고, j가 0 미만이거나 20 초과이면 계산하지 않는다.

 

소스 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
#include <cstring>
using namespace std;
 
long long d[101][21]; // d[i][j] : i번까지 더한 결과 j
int a[101];
int sum = 0;
int main()
{
    int n; scanf("%d"&n);
    memset(d, 0sizeof(d));
    for (int i = 0; i < n-1; i++) { //1 ~ n-1
        scanf("%d"&a[i]);
    }
    scanf("%d"&sum);
    d[0][a[0]] = 1//initial
    for (int i = 1; i < n - 1; i++) { // 1 ~ n-1
        for (int j = 0; j <= 20; j++) { // 0 ~ 20
            if (0<= j + a[i] && j + a[i] <= 20) {
                d[i][j] += d[i - 1][j + a[i]];
            }
            if (j - a[i] >= 0 && j - a[i] <= 20) {
                d[i][j] += d[i - 1][j - a[i]];
            }
        }
    }
    printf("%lld\n", d[n - 2][sum]);
    return 0;
}
cs

 

개발환경 : Visual Studio 2019

지적, 조언 언제든지 환영입니다~~

'백준 문제풀이' 카테고리의 다른 글

백준 9251번 LCS  (0) 2020.02.12
백준 10422번 괄호  (2) 2020.02.12
백준 13975번 파일 합치기 3  (0) 2020.02.12
백준 11066번 파일 합치기  (0) 2020.02.12
백준 2252번 줄 세우기  (0) 2020.02.12