BOJ 부분수열의 합 - 1182

Eye0n·2022년 11월 1일
0

problemSolving

목록 보기
1/2

부분 수열의 합 1182번 문제 풀이에서

첫번째 풀이는 기존에 풀었던 방법을 그대로 적용하면서 for문을 사용하여 몇 개를 선택해 조합하는 식으로 풀었다
그러나 해당 문제에서 의도한 바가 아닌거 같아 다른 방법을 찾았다.

유투브 풀이 영상을 찾게되었는 데,
백트레킹 풀이를 상태공간트리를 만들어가면서 유망한지의 여부에 따라 가지치기를 해주면서 최적의 해를 찾아간다.

여기서 상태공간트리를 어떻게 만들었냐면,
문제에 주어진 "크기가 양수인 부분수열" 이란 구문에서 크기의 범위가 양수이기에 1부터 n까지가 되고 크기의 범위는 결국 조합의 원소 갯수가 되므로 선택의 개수가 된다.
이를 이용하여 선택의 개수에 따라 상태 공간 트리를 채워갔다.

여기서 선택을 더 이해해보자면 숫자를 뽑을 것인지 안뽑을 것인지에 대한 선택이다.
n번째 선택에서 숫자를 뽑는 경우와 안뽑는 경우를 생각하면 된다.
바로 아래 예시를 읽어보자.

n개의 숫자가 주어졌을 때 부분집합의 경우의 수는 2^n개 이다.
(부분수열이나 부분집합이나 같은 맥락이다. 정확히는 같지 않지만 이해하는데 문제가 없을 것이라 생각된다.)

예를 들어 1,2,3 숫자가 주어지면 아래와 같이 2^3 = 8개가 나온다.
공집합, 		--> 3개를 뽑지 않은 선택 (1가지)
1, 2, 3,	 --> 1개를 뽑는 선택 2개는 뽑지 않은 선택 (3가지)
12, 13, 23,  --> 2개를 뽑는 선택 1개는 뽑지 않은 선택 (3가지)
123			 --> 3개를 뽑는 선택 (1가지)

위에서 경우대신 선택이라고 적었는데 숫자를 뽑아 사용하는 경우와 뽑지 않은 경우 2가지에서 선택해야하는 상황이라 경우 단어대신 선택 단어로 적었다.

여기서 숫자의 개수에 따라 그룹화되는 것에 초점을 맞춰 생각해보면
선택의 기회가 주어졌을 때, 숫자를 선택할 것인지 선택하지 않을 것인지 2가지 경우에 따라 그룹된 조합이 만들어진 것을 도출할 수 있다.

그러므로 1개에서 n개까지 뽑는 개수에서 숫자 선택의 기회가 주어지고 선택한 경우와 선택하지 않은 경우로 나눠 진행한다.

위의 것을 가지고 상태 공간 트리를 만들어보면아래와 같이 나온다.

첫번째 선택 1를 뽑는 경우와 안뽑는 경우
0
1   x   --- 1th

두번째 선택은 첫번째의 각 경우에 대해 다음 숫자를 뽑는 경우와 안뽑는 경우
0
1             x
(1 2) (1 x)   (x 2) (x x)   ---- 2th

세번째 선택은 두번째의 각 경우에 대해 다음 숫자를 뽑는 경우와 안뽑는 경우 - 최종 상태 공간 트리
     0
1th  1                                        x
2th  (1 2)             (1 x)                 (x 2)            (x x)
3th  (1 2 3) (1 2 x)   (1 x 3) (1 x x)       (x 2 3) (x 2 x)  (x x 3) (x x x) ---  총 8가지 경우의 수

위의 방법을 가지고 구현한 게 dfs2함수이며 아래 코드로 정의 된다.

let cnt2 = 0;
function dfs2(i, sum) {
  if (i === N) {
    if (sum === S) {
      cnt2++;
    }
    return;
  }

  // 다음 숫자인 nums[i]를 선택한 경우
  dfs2(i + 1, sum + nums[i]);

  // 선택하지 않은 경우
  dfs2(i + 1, sum);
}

// 아무것도 선택하지 않은 경우(공집합)
if (S === 0) cnt2 -= 1;

dfs2(0, 0);
console.log(cnt2);

dfs2의 첫번째 매개변수 i는 다음 선택 기회가 몇번 째인지를 의미하고
문제에서 주어진 부분수열의 합이 S가 되는 경우를 구하기 위해
dfs2의 두번째 매개변수sum에 선택된 숫자를 더해주는데
선택의 기회에서 선택을 할 수도 있고 없고 하니 두 가지 경우에 대해 dfs2함수를 다시 호출시킨다.(재귀호출)

// 입력값
5 0
-7 -3 -2 5 8

// 카운트가 증가될 때의 선택된 숫자들
[ -3, -2, 5 ]  --> 하나씩 선택하는 경우
[] -->  아무것도 선택하지 않은 경우 (공집합) --> 문제 조건 위반 => 카운트 1감소

위의 설명을 보면 입력값이 주어지면 카운드될 때의 선택된 숫자들을 보여주고 있다.
공집합의 경우가 존재하기에 카운트를 1감소 시켜야한다.
아무것도 선택하지 않은 경우 (공집합)을 생각해보면 문제의 조건인 크기가 양수인 부분수열 조건에 위반되므로 S === 0 인 경우에 count를 1 감소 시켜야한다.

참고한 유투브 풀이 영상에서는 유망한지 판단하는 promising함수에서 조건을 더 두어 구현했지만
문제에서 주어진 누적합이 S가 되는 경우와 선택의 횟수가 N이 되는 경우만으로 충분하다 생각되어 추가 구현하지 않았다.

0개의 댓글