07-03 13:09
Recent Posts
Recent Comments
Tags
- ict๊ณต๋ชจ์
- ์คํฝ๋ ํ
- Naver Cloud
- python
- ํ์ด์
- ์กํ๊ณ
- SQL
- ํ๋ก๋ณด๋ ธ
- ์จ์ผ๋ํ
- linux
- mysql
- ์คํฝ์ค๋น
- ํ์ด์ฌ
- ICT๋ฉํ ๋ง
- appetizer
- JOBํ๊ณ
- DB
- Spring
- Java
- API MarketPlace ๊ธ๋ก๋ฒ ์ํฌํฐ์ฆ
- TSQL
- API๋ง์ผํ๋ ์ด์ค
- ์ด๋ธ์
- ํ์ด์๊ณต๋ชจ์
- RaspberryPi
- ์๋์ด๋ ธ
- ์๋ฐ
- DATABASE
- ๋ฐ์ดํฐ๋ฒ ์ด์ค
- ICT
- Today
- Total
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 ;
}
}
'Algorithm > Java' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
Comments