문제

BOJ 1182 부분수열의 합

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

아무것도 뒹굴거리는 거 너무 좋다.
분명 알고를 풀며 뇌를 말랑말랑한 상태로 유지하려 했건만
그러기엔 나는 너무 게으르다.

특히 황금연휴를 지나면서 뒤룩뒤룩 살이 쪘고
(6일 동안 2키로 찜ㅋ 고기+밀가루+과일을 매끼니마다 열심히 챙겨먹었다.)
더욱 게을러졌다.

추석 연휴 후에 일주일에 3알고 완~! 마음을 먹었지만
실제로 먹은 건 혈관이 극혐하고 몸이 극혐하는 개맛도리들뿐...
이것이 연휴 후 처음으로 푼 알고 문제다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	static int n,s,answer;
	static int []arr;
	static int []comb;
	
	public static void main(String[] args)throws Exception{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer(br.readLine());
		
		n=Integer.parseInt(st.nextToken());
		s=Integer.parseInt(st.nextToken());
		
		arr=new int[n];
		
		st=new StringTokenizer(br.readLine());
		for(int i=0;i<n;i++) {
			arr[i]=Integer.parseInt(st.nextToken());
		}
		
		answer=0;
		for(int i=1;i<n+1;i++) {
			comb=new int[i];
			cal(i,0,0,0);
		}
		
		
		System.out.println(answer);
	}
	
	static void cal(int k,int c,int a,int sum) {//k 부분수열에서 뽑을 갯수, c 봅을 인덱스, arr에서 인덱스
		//System.out.println(sum);
		if(c==k&&sum==s) {
			answer++;
			return;
		}
		if(c>=k)return ;
		//if(sum>s)return;
		if(a==n)return;
		
		for(int i=a;i<n;i++) {
			comb[c]=arr[i];
			cal(k,c+1,i+1,sum+arr[i]);
		}
	}
}

이 문제를 풀면서 두 가지의 문제점에 부딪혔다.

1. 부분 수열이 뭐고?

처음엔 당연히 부분 수열? 수열 중에 이어진 부분 말하는 줄ㅋ
띄엄띄엄 가지고 오는 것도 부분 수열인지 몰랐다.
문제 자체를 제대로 이해하지 못한 점

2. 주석처리된 if(sum==s)

왜 그랬는지 이해는 하지 못하겠지만
아마 조금이라도 가지치기를 해서 시간을 줄여보려는 나의 헛된 노력이지 않았을까?
암튼 나는 당연히 4개를 뽑으려는데 2개만에 내가 원하는 결과를 뽑았다? 그럼 굳이 다 볼 필요 없다고 생각했다.
이미 두 개 뽑을 때 카운트는 셌으니깐!

하지만 역시나 내가 생각치 못한 예외는 있는 법
5를 만드려는데 2 3 1 -1
이렇게 있으면 2 3 도 되고 2 3 1 -1 도 된다.

오늘의 교훈

괜히 시간 아낀다고 이상한 코드 집어넣지 말자~~