Home [BaekJoon] 2798 ๋ธ”๋ž™์žญ JAVA
Post
Cancel

[BaekJoon] 2798 ๋ธ”๋ž™์žญ JAVA

๐Ÿ”— ๋ฐฑ์ค€ 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);
    }
}
This post is licensed under CC BY 4.0 by the author.

[BaekJoon] 2108 ํ†ต๊ณ„ํ•™ JAVA

[BaekJoon] 4153 ์ง๊ฐ์‚ผ๊ฐํ˜• JAVA