BOJ 1182 부분수열의 합 [Java]

BOJ 1182 부분수열의 합 [Java]

BOJ 1182 부분수열의 합

1. 문제 링크

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

2. 문제 해설

재귀를 이용해서 풀었다. 각 원소마다 더할 것인지 더하지 않을 것인지를 선택할 수 있고 그에 따라 재귀 함수가 계속 호출된다.

그러므로 시간복잡도는 O(2^n)이다. 최악의 경우에 n이 20이기에 주어진 시간 안에 충분히 해결할 수 있다.

재귀 함수의 매개 변수로 idx와 sum을 주어 현재 몇번째 idx에 위치해있고, 더한 값이 얼마인지를 담았다.

재귀 함수의 탈출 조건은 idx가 n과 같아지면 탈출하고, 만약 sum이 s와 일치하면 경우의 수 값 cnt를 +1 해준다.

문제 조건에서 부분수열의 크기가 양수여야하는 조건이 있으므로 만약 s가 0이라면 아무 것도 더해주지 않은 경우를 빼줘야한다.

그러므로 s가 0이면 cnt에서 -1을 해주고 아니면 cnt를 출력하면 된다.

3. 코드 보기

import java.io.*; import java.util.StringTokenizer; public class Main { static int n, s; static int cnt, ans; static int[] arr; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); 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()); } DFS(0, 0); if (s == 0) { ans = cnt - 1; } else { ans = cnt; } bw.write(Integer.toString(ans)); br.close(); bw.flush(); bw.close(); } static void DFS(int sum, int idx) { if (idx == n) { if (sum == s) { cnt++; } return; } DFS(sum, idx + 1); DFS(sum + arr[idx], idx + 1); } }

from http://jun-codinghistory.tistory.com/220 by ccl(A) rewrite - 2021-11-26 13:28:09