문제
문제 읽기
N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 출력하는 문제입니다. 더 쉽게 이해해보면 부분수열을 선택했을 때 S값이 나올 수 있는 경우의 수를 체크하라는 의미로 받아들이셔도 좋을 것 같습니다. 혹시나 부분수열에 대한 설명도 맨 마지막에 작성해두었으니, 참고해주세요
문제 이해하기 (필요한 변수 정리)
이 문제를 해결하기 위해 필요한 변수는 입력으로 들어오는 N, S 그리고 배열 형태의 데이터를 저장해줄 int형 array와 마지막으로 부분수열의 갯수를 저장할 answer 변수가 필요합니다.
static int N, S, answer;
static int[] array;문제 파악하기 (시간 복잡도 계산)
먼저 시간복잡도를 체크하기 위해 N, S의 입력범위를 기준으로 가능한 최대, 최소 정답에 맞는 데이터를 계산 해보면 int형 자료형으로 충분히 계산할 수 있는 범위입니다.
문제에서 크기가 양수인 부분수열 중에서 답을 구하라고 했기 때문에 공집합은 포함되지 않습니다.
1차 실패 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class BOJ_1182 {
static int N, S, answer;
static int[] array, selected;
private static void rec_func(int k) {
if (k == array.length) {
int value = calculate();
if (value == S) answer++;
} else {
for (int cand = 1; cand <= N; cand++) {
selected[cand] = 1;
rec_func(k + 1);
selected[cand] = 0;
}
}
}
private static int calculate() {
int value = 0;
for (int i = 1; i <= N; i++) {
value = selected[i];
}
return value;
}
public static void main(String[] args) throws IOException {
input();
rec_func(1);
System.out.println(answer);
}
private static void input() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
N = Integer.parseInt(st.nextToken());
S = Integer.parseInt(st.nextToken());
answer = 0;
array = new int[N + 1];
selected = new int[N + 1];
st = new StringTokenizer(br.readLine(), " ");
for (int i = 1; i <= N; i++) {
array[i] = Integer.parseInt(st.nextToken());
}
}
}
실행결과
5 0
-7 -3 -2 5 8
1876틀린 이유
- cand 반복문 초기식 오류
- calculate 메소드에 입력받는 파라미터 k 값 설정 오류
k + 1을 재귀적으로 호출하기 때문에 N보다 커지게 되고 결국 ArrayIndexOutofBoundsException 발생 (탈출조건 실패)
2차 실패 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class BOJ_1182 {
static int N, S, answer;
static int[] array, selected;
private static void rec_func(int k) {
if (k == N) {
int value = calculate(k);
if (value == S) {
answer++;
}
} else {
for (int cand = k; cand <= N; cand++) {
selected[cand] = 1;
rec_func(k + 1);
selected[cand] = 0;
}
}
}
private static int calculate(int k) {
int value = 0;
for (int i = 1; i <= k; i++) {
value += array[i];
}
return value;
}
public static void main(String[] args) throws IOException {
input();
rec_func(1);
System.out.println(answer);
}
private static void input() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
N = Integer.parseInt(st.nextToken());
S = Integer.parseInt(st.nextToken());
answer = 0;
array = new int[N + 1];
selected = new int[N + 1];
st = new StringTokenizer(br.readLine(), " ");
for (int i = 1; i <= N; i++) {
array[i] = Integer.parseInt(st.nextToken());
}
}
}
실행결과
5 0
-7 -3 -2 5 8
0틀린 이유
- calculate 로직 오류
- 부분수열을 구하면서 n번째 수가 포함될 것인가/포함되지 않을 것인가를 체크하는 로직을 제대로 구현하지 못했음
성공 및 해설 코드
package me.jeongseok.cote.fastcampus.bruteforce_hard;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class BOJ_1182 {
static int N, S, answer;
static int[] array;
private static void rec_func(int k, int value) {
if (k == N + 1) {
if (value == S) {
answer++;
}
} else {
// K번째 원소를 포함시킬지 결정하고 재귀호출
// 포함시킬 경우
// K번째 원소까지 다 더한 수
rec_func(k + 1, value + array[k]);
// 포함시키지 않을 경우
// K - 1번째 원소까지 다 더한 수
rec_func(k + 1, value);
}
}
public static void main(String[] args) throws IOException {
input();
rec_func(1, 0);
if (S == 0) {
answer--;
}
System.out.println(answer);
}
private static void input() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
N = Integer.parseInt(st.nextToken());
S = Integer.parseInt(st.nextToken());
answer = 0;
array = new int[N + 1];
st = new StringTokenizer(br.readLine(), " ");
for (int i = 1; i <= N; i++) {
array[i] = Integer.parseInt(st.nextToken());
}
}
}
실패 이유 분석
부분수열을 다 구해서 보면 결국에는 -7이 포함된 것과 포함되지 않은 것, ...5가 포함된 것과 포함되지 않은 것, 8이 포함된것과 포함되지 않은 것 이렇게 각 원소에 대해 2가지 형태로 나뉩니다.
결국 이 부분을 생각조차 하지 못했기 때문에 정답 코드와 전혀 다른 코드가 나오지 않았을까? 라는 생각을 조심스럽게 해봤습니다..
문제를 풀면서 배운 개념
부분 수열
- 하나의 수열의 집합이 있다면 그 중에서 부분부분의 수열을 말한다.
- 예제의 {-7 -3 -2 5 8} 의 부분수열은 {}, {-7}, {-7 -3}, {-7 -3 -2}, ....., {-7 -2}, {-7 -2 5}, {-7 -2 8},....,{-3 5 8}, ..., {5 8} 이런 순서가 지켜진 모든 수열을 부분수열이라고 한다.
- {-3, -7, 8} 이런식으로 원래 수열과 순서가 다르다면 부분수열이라고 할 수 없다.
