[백준/C++] 5557 - 1학년

풀이 시간: 01:58:30

시간 복잡도: O(21n) → O(n) : 숫자의 개수 n개와 가능한 결과의 범위가 0~20 (상수항 무시)

공간 복잡도: O(21n) → O(n) : 2차원 벡터 크기 n * 21 (상수항 무시)

참고: https://velog.io/@lacram/C-백준-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 이하이다.

문제 풀이

먼저 문제를 읽고 분석을 해보았다.

 

n의 범위는 3 이상 100 이하이고, (+)와 (-)로 만들 수 있는 식의 총 개수는 각 위치별로 (+), (-)가 놓일 수 있으므로, 

n = 3이면, 2^3개

n = 11이면, 2^11개

...

n = 100이면 2^100개

 

그리고, 이 중 0 이상 20 이하인 것들의 수이면서 마지막 숫자가 올바르게 반환되는 등식의 개수를 구하면 된다.

 

즉, 본 문제는 n-2번째 숫자까지 사용하여, 마지막 값 k가 나오는 경우의 수를 구하면 된다. 

 

예를 들어, 정수 n개의 각 숫자를 받는 배열 arr를 선언했다고 치자.

arr에는 만약 총 5개의 숫자 45678이 들어갔다고 하면 다음과 같이 구성이 된다.

 

idx	0	1	2	3	4
value	4	5	6	7	8

 

일단 해당 값들 중 첫 번째 인덱스의 값은 연산자 (+), (-)와 관계 없이 무조건 등식에 포함이 되므로 인덱스 0의 값은 제외하고, 또 마지막 인덱스의 값은 등식의 마지막에 반환되는 값을 의미하므로 해당 값도 제외를 한다.

 

그러면 우리가 고려해야할 부분은 정수 5개 중 idx 1 ~ idx 3까지이다.

이를 수식으로 나타내면 우리는 정수 n개 중 idx 1 ~ idx (n-2) 까지를 고려하여 계산하면 되는 것이다.

 

이 다음부터는 0 이상 20 이하인 것들의 수만 추출하는 조건을 작성해보았다.

if(arr[i] + arr[i+1] <= 20) : 이전 값과 다음 값을 더하였을 때 20 이하인 경우

if(arr[i] - arr[i+1] >= 0) : 이전 값과 다음 값을 뺐을 때 0 이상인 경우

 

그리고 나서 각 올바른 등식의 경우의 수를 저장하는 것을 어떻게 해야하는지에서 막히게 되었다.

이 이후로 더 생각을 해보았는데, 제대로 풀리지 않는 느낌이 들어서 솔루션을 참고하게 되었다.

 

알고보니 2차원 배열을 하나 더 생성을 하여 각각의 경우의 수를 점화식으로 더하여 저장하는 것이었다.

 

그래서 dp라는 2차원 벡터를 선언하여 다음과 같이 정의하였다.

dp[i][j] = "i번째 숫자까지 사용하여 j를 만드는 경우의 수를 저장한 값"

 

아까 위에 언급했다시피, 0번째 숫자는 따로 저장을 해주었다.

dp[0][arr[0]] = 1

이 코드의 의미는 0번째 숫자를 사용하여 첫 번째 숫자 arr[0]을 만드는 경우의 수는 1가지라는 뜻이다.

즉, 자기 자신은 자기 자신을 만드는 경우의 수가 1가지라는 것이기 때문에 1로 저장하였다.

 

그리고 난 후 이중 for문을 통해 idx 1 ~ (n-2) 번째의 숫자까지, 즉 맨 첫 번째 숫자와 맨 마지막 숫자를 제외하고, j(arr[i])의 값이  0 이상 20 이하의 경우만 고려하여 계산을 하였다.

for (int i = 1; i < n - 1; i++) {
	for (int j = 0; j <= 20; j++) {
    	...
	}
}

 

먼저 if문을 통해 이전 단계에서 숫자 j를 만들 수 있는 경우의 수가 존재하는지 확인해야 한다. 

이전 단계까지의 숫자들을 사용하여 숫자 j 즉, 0 이상 20 이하의 숫자를 만들 수 있는 경우의 수가 존재해야 다음 숫자를 사용해 계산이 가능하기 때문이다.

 

그리고, 현재까지 만든 숫자 j에 현재 숫자인 arr[i] 값을 더하거나 뺐을 때 0 이상이거나 20 이하인 경우를 확인한다.

만약 참이면, 각각 arr[i] 값을 더하거나 뺀 배열 dp에, 이전 단계에서 j를 만드는 경우의 수를 더해준다.

if (dp[i - 1][j]) {
	if (j + arr[i] <= 20)
    		dp[i][j + arr[i]] += dp[i - 1][j];
	if (j - arr[i] >= 0)
    		dp[i][j - arr[i]] += dp[i - 1][j];
}

 

그리고 마지막으로 (n-2) 번째의 숫자까지 사용하여, 마지막 숫자 arr[n-1]를 만드는 경우의 수를 출력해준다.

dp[n-2][arr[n-1]]

전체 코드

#include <iostream>
#include <vector>
using namespace std;

int n;
vector<int> arr; // 벡터 arr 생성
vector<vector<long long>> dp; // 2차원 벡터 dp 생성

int main(void)
{
   ios_base::sync_with_stdio(false);
   cin.tie(NULL);
   cout.tie(NULL);
   cin >> n;

   arr.resize(n, 0); // 크기가 n인 벡터를 모두 0으로 초기화
   dp.resize(n, vector<long long>(21, 0)); // 크기가 n x 21인 벡터를 모두 0으로 초기화

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

   // dp[i][j] = "i번째 숫자까지 사용하여 j를 만드는 경우의 수"
   // dp[0][arr[0]] = 1 -> 0번째 숫자를 사용하여 첫 번째 숫자인 arr[0]을 만드는 경우의 수는 1가지
   dp[0][arr[0]] = 1;

   for (int i = 1; i < n - 1; i++) { // 1~(n-2)번째의 숫자까지, 즉 맨 첫번째 숫자와 맨 마지막 숫자를 제외한 모든 값
      for (int j = 0; j <= 20; j++) { // 0 이상 20 이하의 경우만 고려
         if (dp[i - 1][j]) { // 이전 단계에서 숫자 j를 만들 수 있는 경우가 존재하는지 확인
            if (j + arr[i] <= 20) // 현재까지 만든 숫자 j에 현재 숫자 arr[i]를 더했을 때 20 이하인 경우
               dp[i][j + arr[i]] += dp[i - 1][j]; // 이전 단계에서 j를 만드는 경우의 수를 더함
            if (j - arr[i] >= 0) // 현재까지 만든 숫자 j에 현재 숫자 arr[i]를 뺐을 때 0 이상인 경우
               dp[i][j - arr[i]] += dp[i - 1][j]; // 이전 단계에서 j를 만드는 경우의 수를 더함 
         }
      }
   }
   // (n-2)번째의 숫자까지를 사용하여, 마지막 숫자 arr[n-1]를 만드는 경우의 수 출력
   cout << dp[n - 2][arr[n - 1]] << "\n";
}

 

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

5557번: 1학년