๋ฐ์ํ
๋ฌธ์
SWEA(SW Expert Academy) 3234๋ฒ ์คํ์ด์ ์ํ์ ์ธ [D4]
ํ์ด
์ํ์ ์ธ์ ์ฌ๋ฆฌ๋ ์์ ์ ํ๊ธฐ => ์์ด
์ด๋์ชฝ์ ์ฌ๋ฆด์ง ์ ํ๊ธฐ => ๋ถ๋ถ์งํฉ
๋ฌด๊ฒ๋ฅผ ์ ๋ ฅ๋ฐ์ ์ฐ์ ์ฌ๋ ค๋์ ์์๋ฅผ ์ ํจ.
sorted๋ฐฐ์ด์ ์คํ์๋ฃ ๋ ์์ด์ ์ ์ฅํ๋ฉฐ, ์์ด์ด ์์ฑ๋์์ ๊ฒฝ์ฐ(cnt==N) ์ด๋์ชฝ์ ์ฌ๋ฆด์ง ์ ํจ.
ํ์ฌ ์ถ๋ฅผ ์ค๋ฅธ์ชฝ์ ์ฌ๋ฆฌ๋ ๊ฒฝ์ฐ, ์ผ์ชฝ์ ์ฌ๋ฆฌ๋ ๊ฒฝ์ฐ๋ฅผ ๊ฐ๊ฐ ์คํ.
์คํ๋์ค left<right์ผ ๊ฒฝ์ฐ, ๊ฐ์ง์น๊ธฐ๋ฅผ ํตํด ์๊ฐ์ ๋จ์ถ (๋ฐฑํธ๋ํน)
๊ธฐ์ ์กฐ๊ฑด์ ๋ง์กฑํ ๊ฒฝ์ฐ, ๊ฒฝ์ฐ์ ์๋ฅผ ์ฆ๊ฐ์ํจ ํ ์ข ๋ฃ
์ฝ๋
import java.io.*;
import java.util.*;
public class Solution{
static int N, res;
static int[] weight,sorted;
static boolean[] isSelected;
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int tc = Integer.parseInt(br.readLine());
for(int T = 1 ; T<=tc ; T++) {
N = Integer.parseInt(br.readLine());
weight = new int[N];
sorted = new int[N];
isSelected = new boolean[N];
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
for(int i =0 ; i < N ; i++) {
weight[i] = Integer.parseInt(st.nextToken());
}
res = 0;
perm(0);
sb.append("#").append(T).append(" ").append(res).append("\n");
}
System.out.println(sb.toString());
br.close();
}
//์ผ์ชฝ, ์ค๋ฅธ์ชฝ ๊ด๊ณ์์ด ์ฌ๋ ค๋๋ ์์๋ฅผ ์ ํ๋ '์์ด'ํจ์
private static void perm(int cnt) {
if(cnt == N) { //๊ธฐ์ ์กฐ๊ฑด
scale(0,0,0);
}
//์์ด ๋ง๋ค๊ธฐ
for(int i = 0 ; i < N ; i++) {
if(isSelected[i]) continue;
sorted[cnt] = weight[i]; //sorted: ์์ด๊ฒฐ๊ณผ๋ฅผ ์ ์ฅ(์ธ๋ฑ์ค ์ ์ฅ์ด ์๋ ๊ฐ ์ ์ฅ)
isSelected[i] = true; // ํ์ฌ ์ธ๋ฑ์ค ์ ํ์ฒ๋ฆฌ
perm(cnt+1);
isSelected[i] = false; // ์ ํ ์ฒ๋ฆฌ ์ด๊ธฐํ
}
}
//์์ดํจ์์ ๊ฒฐ๊ณผ๊ฐ์ ์ด์ฉํด์ ์ํ์ ์ธ์ ์ฌ๋ฆด ๊ฒฝ์ฐ์ ์๋ฅผ ๊ณ์ฐํ๋ '๋ถ๋ถ์งํฉ'ํจ์
private static void scale(int cnt, int left, int right) {
if(left<right) return; //๊ฐ์ง์น๊ธฐ(ํ์ฌ ์ผ์ชฝ์ ๋ฌด๊ฒ๋ณด๋ค ์ค๋ฅธ์ชฝ์ ๋ฌด๊ฒ๊ฐ ๋ง์ ๋)
if(cnt == N) { //๊ธฐ์ ์กฐ๊ฑด
res++; //๊ฒฝ์ฐ์ ์ ์ฆ๊ฐ
return;
}
scale(cnt+1, left, right+sorted[cnt]); //์ค๋ฅธ์ชฝ์ ์ฌ๋ ธ์ ๋
scale(cnt+1, left+sorted[cnt], right); //์ผ์ชฝ์ ์ฌ๋ ธ์ ๋
}
}
๋ฐ์ํ
'๐ ์๊ณ ๋ฆฌ์ฆ > BruteForce' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[๋ฐฑ์ค] 14658๋ฒ: ํ๋์์ ๋ณ๋ฅ๋ณ์ด ๋น๋ฐ์น๋ค (Java) (0) | 2022.04.12 |
---|---|
[๋ฐฑ์ค] 6987๋ฒ ์๋์ปต(Java) (0) | 2022.02.08 |
[SWEA] 4012๋ฒ ์๋ฆฌ์ฌ, [๋ฐฑ์ค] 14889๋ฒ ์คํํธ์ ๋งํฌ (0) | 2021.08.18 |
[๋ฐฑ์ค] 2961๋ฒ ๋์์ด๊ฐ ๋ง๋ ๋ง์๋ ์์ (0) | 2021.08.17 |
[๋ฐฑ์ค]17281๋ฒ โพ(์ผ๊ตฌ) (0) | 2021.08.17 |