[Algorithm] ๐๋ฐฑ์ค 2798 ๋ธ๋์ญ
0. ๋ฌธ์
์นด์ง๋ ธ์์ ์ ์ผ ์ธ๊ธฐ ์๋ ๊ฒ์ ๋ธ๋์ญ์ ๊ท์น์ ์๋นํ ์ฝ๋ค. ์นด๋์ ํฉ์ด 21์ ๋์ง ์๋ ํ๋ ๋ด์์, ์นด๋์ ํฉ์ ์ต๋ํ ํฌ๊ฒ ๋ง๋๋ ๊ฒ์์ด๋ค. ๋ธ๋์ญ์ ์นด์ง๋ ธ๋ง๋ค ๋ค์ํ ๊ท์ ์ด ์๋ค.
ํ๊ตญ ์ต๊ณ ์ ๋ธ๋์ญ ๊ณ ์ ๊น์ ์ธ์ ์๋ก์ด ๋ธ๋์ญ ๊ท์น์ ๋ง๋ค์ด ์๊ทผ, ์ฐฝ์์ด์ ๊ฒ์ํ๋ ค๊ณ ํ๋ค.
๊น์ ์ธ ๋ฒ์ ์ ๋ธ๋์ญ์์ ๊ฐ ์นด๋์๋ ์์ ์ ์๊ฐ ์ฐ์ฌ ์๋ค. ๊ทธ ๋ค์, ๋๋ฌ๋ N์ฅ์ ์นด๋๋ฅผ ๋ชจ๋ ์ซ์๊ฐ ๋ณด์ด๋๋ก ๋ฐ๋ฅ์ ๋๋๋ค. ๊ทธ๋ฐ ํ์ ๋๋ฌ๋ ์ซ์ M์ ํฌ๊ฒ ์ธ์น๋ค.
์ด์ ํ๋ ์ด์ด๋ ์ ํ๋ ์๊ฐ ์์ N์ฅ์ ์นด๋ ์ค์์ 3์ฅ์ ์นด๋๋ฅผ ๊ณจ๋ผ์ผ ํ๋ค. ๋ธ๋์ญ ๋ณํ ๊ฒ์์ด๊ธฐ ๋๋ฌธ์, ํ๋ ์ด์ด๊ฐ ๊ณ ๋ฅธ ์นด๋์ ํฉ์ M์ ๋์ง ์์ผ๋ฉด์ M๊ณผ ์ต๋ํ ๊ฐ๊น๊ฒ ๋ง๋ค์ด์ผ ํ๋ค.
N์ฅ์ ์นด๋์ ์จ์ ธ ์๋ ์ซ์๊ฐ ์ฃผ์ด์ก์ ๋, M์ ๋์ง ์์ผ๋ฉด์ M์ ์ต๋ํ ๊ฐ๊น์ด ์นด๋ 3์ฅ์ ํฉ์ ๊ตฌํด ์ถ๋ ฅํ์์ค.
์ ๋ ฅ
์ฒซ์งธ ์ค์ ์นด๋์ ๊ฐ์ N(3 โค N โค 100)๊ณผ M(10 โค M โค 300,000)์ด ์ฃผ์ด์ง๋ค. ๋์งธ ์ค์๋ ์นด๋์ ์ฐ์ฌ ์๋ ์๊ฐ ์ฃผ์ด์ง๋ฉฐ, ์ด ๊ฐ์ 100,000์ ๋์ง ์๋ ์์ ์ ์์ด๋ค.
ํฉ์ด M์ ๋์ง ์๋ ์นด๋ 3์ฅ์ ์ฐพ์ ์ ์๋ ๊ฒฝ์ฐ๋ง ์ ๋ ฅ์ผ๋ก ์ฃผ์ด์ง๋ค.
์ถ๋ ฅ
์ฒซ์งธ ์ค์ M์ ๋์ง ์์ผ๋ฉด์ M์ ์ต๋ํ ๊ฐ๊น์ด ์นด๋ 3์ฅ์ ํฉ์ ์ถ๋ ฅํ๋ค.
1. ๋ฌธ์ ๊ฐ๋จ ํด์
N๊ฐ์ ์นด๋ ์ค 3๊ฐ๋ฅผ ์ ํํ๊ณ ์ด๋ฅผ ํฉ์ณ์ M์ ์ต๋ํ ๊ฐ๊น์ด ๊ฒฐ๊ณผ๋ฅผ ๊ตฌํด๋ผ
2. ์์ด๋์ด
3๊ฐ์ ์นด๋๋ฅผ ๋ํด์ M๋ณด๋ค๋ ์์ผ๋ฉด์ ์ ์ผ ํฐ ๊ฐ ๊ตฌํ๊ธฐ
์ฌ๊ท๋ฅผ ์ด์ฉํ ์์ ํ์ (dfs)
3. ํต์ฌ ํ์ด
1) 3๊ฐ์ ์นด๋๋ฅผ ๋ํด์ M๋ณด๋ค๋ ์์ผ๋ฉด์ ์ ์ผ ํฐ ๊ฐ ๊ตฌํ๊ธฐ
ret = Math.max(ret, check());
// check() ํจ์๋ M๋ณด๋ค ์์ ํฉ ๋ฐํ
// M๋ณด๋ค ํฌ๋ฉด -1๋ฐํ
2) ์ฌ๊ทํจ์๋ฅผ ์ด์ฉํ์ฌ ๋ชจ๋ ๊ฒฝ์ฐ๋ฅผ ํ์
result[i] = true;
dfs(depth+1, i+1);
result[i] = false;
4. ์ฝ๋
import java.util.Scanner;
public class BOJ_2798 {
static int N,M, arr[];
static boolean result[];
static int ret = 0;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
M = sc.nextInt();
arr = new int[N];
result = new boolean[N];
for(int i=0; i<N; i++)
arr[i] = sc.nextInt();
dfs(0,0);
System.out.println(ret);
}
public static void dfs(int depth, int start) {
if(depth == 3) {
ret = Math.max(ret, check());
return;
}
for(int i=start; i<N; i++) {
result[i] = true;
dfs(depth+1, i+1);
result[i] = false;
}
}
public static int check() {
int sum = 0;
for(int i=0; i<N; i++) {
if(result[i])
sum+=arr[i];
}
if(sum > M)
return -1;
else
return sum;
}
}
5. ๊ฒฐ๊ณผ
์ฑ๊ณต~
Author And Source
์ด ๋ฌธ์ ์ ๊ดํ์ฌ([Algorithm] ๐๋ฐฑ์ค 2798 ๋ธ๋์ญ), ์ฐ๋ฆฌ๋ ์ด๊ณณ์์ ๋ ๋ง์ ์๋ฃ๋ฅผ ๋ฐ๊ฒฌํ๊ณ ๋งํฌ๋ฅผ ํด๋ฆญํ์ฌ ๋ณด์๋ค https://velog.io/@kha0318/Algorithm-๋ฐฑ์ค-2798-๋ธ๋์ญ์ ์ ๊ท์: ์์์ ์ ๋ณด๊ฐ ์์์ URL์ ํฌํจ๋์ด ์์ผ๋ฉฐ ์ ์๊ถ์ ์์์ ์์ ์ ๋๋ค.
์ฐ์ํ ๊ฐ๋ฐ์ ์ฝํ ์ธ ๋ฐ๊ฒฌ์ ์ ๋ (Collection and Share based on the CC Protocol.)
์ข์ ์นํ์ด์ง ์ฆ๊ฒจ์ฐพ๊ธฐ
๊ฐ๋ฐ์ ์ฐ์ ์ฌ์ดํธ ์์ง
๊ฐ๋ฐ์๊ฐ ์์์ผ ํ ํ์ ์ฌ์ดํธ 100์ ์ถ์ฒ ์ฐ๋ฆฌ๋ ๋น์ ์ ์ํด 100๊ฐ์ ์์ฃผ ์ฌ์ฉํ๋ ๊ฐ๋ฐ์ ํ์ต ์ฌ์ดํธ๋ฅผ ์ ๋ฆฌํ์ต๋๋ค