[백준] 1182 - 부분수열의 합 (JAVA)

1. 소요시간 : 10분
2. 문제 사이트 : 백준
3. 문제 수준 : 실버2
4. 문제 유형 : 브루트포스 알고리즘, 백트래킹
5. 다른 사람의 풀이를 참고 했는가 ? : X
6. 한 번 풀었다가 다시 푸는 문제인가 ? : X
7. 문제 링크 : https://www.acmicpc.net/problem/1182
8. 푼 날짜 : 2023.03.06

1. 사용한 자료구조 & 알고리즘

백트래킹을 사용했다.

2. 풀이과정

백트래킹을 사용해서 모든 경우의 수를 탐색했다. 전체적으로 5분만에 짰으나 한 가지 예외가 발생했는데 테스트케이스의 경우에 출력이 1이 되어야 했지만 2가 나왔었다. 그래서 원인을 찾지 못해서 계속 생각해보다가 depth가 0일 때에도 우리가 원하는 값이 0이므로 count가 증가되고 있었다. 그래서 count가 2가 나왔었고, depth가 0일 때에는 count를 증가시켜주지 않는 방법으로 해결했다. 만약 테스트케이스에서 우리가 원하는 s의 값이 0이 아니라 다른 값이었다면, 더 오래 걸렸을 것으로 예상한다.
테스트케이스덕분에 쉽게 예외를 발견할 수 있었다.

사실 이전에도 비슷한 이유로 더 헤맨 적이 있었는데, 같은 원인으로 발목을 잡혔다. 이번 기회에 확실하게 알아두어야겠다.

3. 소스코드

import java.util.*;
import java.io.*;
public class Main{
	static boolean visited[];
	static int arr[];
	static int cnt=0;
	public static void main(String[] args) throws IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb=new StringBuilder();
		StringTokenizer st;
		
		st=new StringTokenizer(br.readLine());
		int n=Integer.parseInt(st.nextToken());
		int s=Integer.parseInt(st.nextToken());
		arr=new int[n];
		visited=new boolean[n];
		String line[]=br.readLine().split(" ");
		for(int i=0;i<arr.length;i++) {
			arr[i]=Integer.parseInt(line[i]);
		}
		dfs(0,0,s,0);
		System.out.println(cnt);

	}
	public static void dfs(int depth,int now,int purpose,int start) {
		if(now==purpose&&depth!=0) {
			cnt++;
		}
		if(depth>=visited.length)
			return;
		
		for(int i=start;i<visited.length;i++) {
			if(!visited[i]) {
				visited[i]=true;
				dfs(depth+1,now+arr[i],purpose,i+1);
				visited[i]=false;
			}
		}
		
	}
}

4. 결과

5. 회고

슬슬 백트래킹의 사용에도 많이 익숙하다.
하루에 백준 1문제 이상 푸는 것을 목표로 하고 있다.
https://solved.ac/profile/anwlro0212