07-03 13:09
Recent Posts
Recent Comments
๊ด€๋ฆฌ ๋ฉ”๋‰ด

miinsun

[Algorithm]์•Œ๊ณ ๋ฆฌ์ฆ˜ ์ž๋ฐ”_54 ํ•ฉ์ด ๊ฐ™์€ ๋ถ€๋ถ„ ์ง‘ํ•ฉ(DFS : ์•„๋งˆ์กด ์ธํ„ฐ๋ทฐ) ๋ณธ๋ฌธ

Algorithm/Java

[Algorithm]์•Œ๊ณ ๋ฆฌ์ฆ˜ ์ž๋ฐ”_54 ํ•ฉ์ด ๊ฐ™์€ ๋ถ€๋ถ„ ์ง‘ํ•ฉ(DFS : ์•„๋งˆ์กด ์ธํ„ฐ๋ทฐ)

miinsun 2022. 2. 3. 18:30

 

๐Ÿ’ฌ ๋ฌธ์ œ ์„ค๋ช…

N๊ฐœ์˜ ์›์†Œ๋กœ ๊ตฌ์„ฑ๋œ ์ž์—ฐ์ˆ˜ ์ง‘ํ•ฉ์ด ์ฃผ์–ด์ง€๋ฉด, ์ด ์ง‘ํ•ฉ์„ ๋‘ ๊ฐœ์˜ ๋ถ€๋ถ„์ง‘ํ•ฉ์œผ๋กœ ๋‚˜๋ˆ„์—ˆ์„ ๋•Œ, ๋‘ ๋ถ€๋ถ„ ์ง‘ํ•ฉ์˜ ์›์†Œ์˜ ํ•ฉ์ด ์„œ๋กœ ๊ฐ™์€ ๊ฒฝ์šฐ๊ฐ€ ์กด์žฌํ•˜๋ฉด “YES"๋ฅผ ์ถœ๋ ฅํ•˜๊ณ , ๊ทธ๋ ‡์ง€ ์•Š์œผ๋ฉด ”NO"๋ฅผ ์ถœ๋ ฅํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์„ธ์š”.

๋‘˜๋กœ ๋‚˜๋‰˜๋Š” ๋‘ ๋ถ€๋ถ„์ง‘ํ•ฉ์€ ์„œ๋กœ์†Œ ์ง‘ํ•ฉ์ด๋ฉฐ, ๋‘ ๋ถ€๋ถ„์ง‘ํ•ฉ์„ ํ•ฉํ•˜๋ฉด ์ž…๋ ฅ์œผ๋กœ ์ฃผ์–ด์ง„ ์›๋ž˜์˜ ์ง‘ํ•ฉ์ด ๋˜์–ด ํ•ฉ๋‹ˆ๋‹ค.
์˜ˆ๋ฅผ ๋“ค์–ด {1, 3, 5, 6, 7, 10}์ด ์ž…๋ ฅ๋˜๋ฉด {1, 3, 5, 7} = {6, 10} ์œผ๋กœ ๋‘ ๋ถ€๋ถ„์ง‘ํ•ฉ์˜ ํ•ฉ์ด 16์œผ๋กœ ๊ฐ™์€ ๊ฒฝ์šฐ๊ฐ€ ์กด์žฌํ•˜๋Š” ๊ฒƒ์„ ์•Œ ์ˆ˜ ์žˆ๋‹ค.

 

 

 

๐Ÿ”จ ์ž…์ถœ๋ ฅ ์˜ˆ

์ž…๋ ฅ - ์ฒซ ๋ฒˆ์งธ ์ค„์— ์ž์—ฐ์ˆ˜ N(1<=N<=10)์ด ์ฃผ์–ด์ง‘๋‹ˆ๋‹ค.

๋‘ ๋ฒˆ์งธ ์ค„์— ์ง‘ํ•ฉ์˜ ์›์†Œ N๊ฐœ๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๊ฐ ์›์†Œ๋Š” ์ค‘๋ณต๋˜์ง€ ์•Š๋Š”๋‹ค.

6
1 3 5 6 7 10

์ถœ๋ ฅ - ์ฒซ ๋ฒˆ์งธ ์ค„์— “YES" ๋˜๋Š” ”NO"๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค.

YES
 

 

 

โ€‹

๐Ÿ’ป Solution.java

import java.util.*;

public class Main {
	static int n, total = 0;
	static String answer = "NO";
	boolean flag = false;

	public void DFS(int L, int sum, int[] arr) {
		if(flag) return;
		if(sum > total / 2) return;
		if(L == n) {
			if((total - sum) == sum) {
				answer ="YES";
				flag = true;
			}
		}
		else {
			DFS(L+1, sum+arr[L], arr);
			DFS(L+1, sum, arr);
		}
 	}
	
	public static void main(String[] args){
		Main main = new Main();
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		int[] arr = new int [n];
		
		for(int i = 0; i < n; i++) {
			arr[i] = sc.nextInt();
			total += arr[i];
		}
		
		main.DFS(0, 0, arr);
		System.out.println(answer);
		
		sc.close();
		return ;
	}
}

 

 

 

Comments