๐ ๋ฐฑ์ค 2798 ๋ธ๋์ญ https://www.acmicpc.net/problem/2798
๋ฌธ์
์นด์ง๋ ธ์์ ์ ์ผ ์ธ๊ธฐ ์๋ ๊ฒ์ ๋ธ๋์ญ์ ๊ท์น์ ์๋นํ ์ฝ๋ค. ์นด๋์ ํฉ์ด 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์ฅ์ ํฉ์ ์ถ๋ ฅํ๋ค.
ํ์ด
์กฐ๊ธ์ ๋ฌด์ํ ๋ฐฉ๋ฒ์ผ๋ก.. ํ์๋ค.
๋ฌด๋ ค 3์ค ํฌ๋ฌธ์ผ๋ก ๋ธ๋ฃจํธํฌ์ค๋ฅผ ํตํด ๊ฐ์ ์ํํ์ฌ ๋ชจ๋ ๊ฒฝ์ฐ์ ์๋ฅผ ์ฐพ์ ํ M์ ๊ฐ๊น์ด ์๋ฅผ ๊ตฌํด์คฌ๋ค.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
import java.io.*;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
int sum = 0;
int approx = 0;
int[] nums = new int[n];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) nums[i] = Integer.parseInt(st.nextToken());
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
for (int k = j + 1; k < n; k++) {
sum = nums[i] + nums[j] + nums[k];
if (approx < sum && sum <= m) approx = sum;
}
}
}
System.out.println(approx);
}
}