๋ฌธ์ (์ถ์ฒ: https://www.acmicpc.net/problem/1715)
<์นด๋ ์ ๋ ฌํ๊ธฐ>
๋ฌธ์
์ ๋ ฌ๋ ๋ ๋ฌถ์์ ์ซ์ ์นด๋๊ฐ ์๋ค๊ณ ํ์. ๊ฐ ๋ฌถ์์ ์นด๋์ ์๋ฅผ A, B๋ผ ํ๋ฉด ๋ณดํต ๋ ๋ฌถ์์ ํฉ์ณ์ ํ๋๋ก ๋ง๋๋ ๋ฐ์๋ A+B ๋ฒ์ ๋น๊ต๋ฅผ ํด์ผ ํ๋ค. ์ด๋ฅผํ ๋ฉด, 20์ฅ์ ์ซ์ ์นด๋ ๋ฌถ์๊ณผ 30์ฅ์ ์ซ์ ์นด๋ ๋ฌถ์์ ํฉ์น๋ ค๋ฉด 50๋ฒ์ ๋น๊ต๊ฐ ํ์ํ๋ค.
๋งค์ฐ ๋ง์ ์ซ์ ์นด๋ ๋ฌถ์์ด ์ฑ ์ ์์ ๋์ฌ ์๋ค. ์ด๋ค์ ๋ ๋ฌถ์์ฉ ๊ณจ๋ผ ์๋ก ํฉ์ณ๋๊ฐ๋ค๋ฉด, ๊ณ ๋ฅด๋ ์์์ ๋ฐ๋ผ์ ๋น๊ต ํ์๊ฐ ๋งค์ฐ ๋ฌ๋ผ์ง๋ค. ์๋ฅผ ๋ค์ด 10์ฅ, 20์ฅ, 40์ฅ์ ๋ฌถ์์ด ์๋ค๋ฉด 10์ฅ๊ณผ 20์ฅ์ ํฉ์น ๋ค, ํฉ์น 30์ฅ ๋ฌถ์๊ณผ 40์ฅ์ ํฉ์น๋ค๋ฉด (10 + 20) + (30 + 40) = 100๋ฒ์ ๋น๊ต๊ฐ ํ์ํ๋ค. ๊ทธ๋ฌ๋ 10์ฅ๊ณผ 40์ฅ์ ํฉ์น ๋ค, ํฉ์น 50์ฅ ๋ฌถ์๊ณผ 20์ฅ์ ํฉ์น๋ค๋ฉด (10 + 40) + (50 + 20) = 120๋ฒ์ ๋น๊ต๊ฐ ํ์ํ๋ฏ๋ก ๋ ํจ์จ์ ์ธ ๋ฐฉ๋ฒ์ด๋ค.
N๊ฐ์ ์ซ์ ์นด๋ ๋ฌถ์์ ๊ฐ๊ฐ์ ํฌ๊ธฐ๊ฐ ์ฃผ์ด์ง ๋, ์ต์ํ ๋ช ๋ฒ์ ๋น๊ต๊ฐ ํ์ํ์ง๋ฅผ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
์ ๋ ฅ
์ฒซ์งธ ์ค์ N์ด ์ฃผ์ด์ง๋ค. (1 ≤ N ≤ 100,000) ์ด์ด์ N๊ฐ์ ์ค์ ๊ฑธ์ณ ์ซ์ ์นด๋ ๋ฌถ์์ ๊ฐ๊ฐ์ ํฌ๊ธฐ๊ฐ ์ฃผ์ด์ง๋ค. ์ซ์ ์นด๋ ๋ฌถ์์ ํฌ๊ธฐ๋ 1,000๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ์์ ์ ์์ด๋ค.
์ถ๋ ฅ
์ฒซ์งธ ์ค์ ์ต์ ๋น๊ต ํ์๋ฅผ ์ถ๋ ฅํ๋ค.
๋ฌธ์ ํ์ด
- my solution (JAVA)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
public class _1715_ {
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
int n=Integer.parseInt(bf.readLine());
PriorityQueue<Integer> priorityqueue=new PriorityQueue<>();
for(int i=0; i<n; i++) {
priorityqueue.add(Integer.parseInt(bf.readLine()));
}
int result=0;
while(priorityqueue.size()>1) {
int temp=priorityqueue.poll()+priorityqueue.poll();
result+=temp;
priorityqueue.add(temp);
}
System.out.println(result);
}
}
- ์ ๋ ฅ๋ฐ์ ํ ์ฐ์ ์์ ํ์ ์ ์ฅ
- ์ฐ์ ์์ ํ์ ํฌ๊ธฐ๊ฐ 1๋ณด๋ค ํด ๋ ์นด๋ ๋ฌถ์์ ๋น๊ตํ ์ ์์
- ์ฐ์ ์์ ํ์ด๊ธฐ ๋๋ฌธ์ poll๋ก ๊บผ๋ด๋ฉด ์์ ๊ฐ์ ๊บผ๋ผ ์ ์์
- 2๊ฐ๋ฅผ ๊บผ๋ด ํฉ์ ๊ตฌํ ํ result์ ๋ํด์ฃผ๊ณ ์ฐ์ ์์ ํ์๋ ๋ค์ ๋ฃ์ด์ค
- ๋ค์ ๊ฐ์ ๊ณ์ฐํ ๋ ๋ฐฉ๊ธ ๊ตฌํ ๊ฐ๋ณด๋ค ์์ ๊ฐ์ด ์์ ์ ์๊ธฐ ๋๋ฌธ
โ ์ฒ์์ ์ ๋ฐฐ์ด์ ์ฌ์ฉํ๋๊ฐ?
๋จ์ํ ๋ฐฐ์ด์ ์ ์ฅํ ํ ์ ๋ ฌ์ ์ฌ์ฉํ์ฌ ์์์๋ถํฐ ๊ณ์ํด์ ๋ํด์ฃผ๋ฉด ๋๋ ๋ฌธ์ ์ธ ์ค ์์๋ค.
ํ์ง๋ง, ์นด๋ ๋ฌถ์์ ์๊ฐ ๋ง์ ๋ ๋ฐฉ๊ธ ๊ตฌํ ๊ฐ ๋ณด๋ค ์์ ๊ฐ๋ค์ด ์์ ์ ์๊ธฐ ๋๋ฌธ์ ๊ณ์ํด์ ์์ ๊ฐ์ ์ฐพ์์ค์ผ ํ๋ค๋ ๊ฒ์ ์ ์ ์์๋ค.
โ 1์ ์ ๋ ฅ์ผ๋ก ๋ฐ์์ ๋?
๋น์ฐํ 1๋ก ์ ๋ ฅ๋ฐ์ ์นด๋ ๋ฌถ์์ ์๊ฐ ๋ต์ธ์ค ์์๋ค. ํ์ง๋ง 1์ ์ ๋ ฅ์ผ๋ก ๋ฐ์ผ๋ฉด ์นด๋ ๋ฌถ์๋ผ๋ฆฌ ๋น๊ตํ ํ์๊ฐ ์์ผ๋ฏ๋ก ๋ต์ 0์ด ์ถ๋ ฅ๋์ด์ผ ํ๋ค.
์๊ฐ๐ค
๋ฌธ์ ๋ง ๋ณด๊ณ ์ฐ์ ์์ ํ๋ฅผ ์ฌ์ฉํด์ผ ํ๋ค๋ ๊ฒ์ ์ด๋ป๊ฒ ์ ์ ์์๊น..
'๐Algorithm > ๐ฅBaekjoon' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[Baekjoon] 2206_๋ฒฝ ๋ถ์๊ณ ์ด๋ํ๊ธฐ (0) | 2022.10.23 |
---|---|
[Baekjoon] 1759_์ํธ ๋ง๋ค๊ธฐ (0) | 2022.08.15 |
[Baekjoon] 15649, 15650, 15651, 15652 N๊ณผ M (0) | 2022.08.03 |
[Baekjoon] 2564_๊ฒฝ๋น์ (0) | 2022.06.10 |
[Baekjoon] 3184_์ (0) | 2022.06.02 |