Greedy(3)
-
BOJ 2516 : 원숭이
https://www.acmicpc.net/problem/2516 2516번: 원숭이 첫째 줄에는 원숭이들의 수를 나타내는 하나의 정수 N이 주어진다. 단, N은 3이상 100,000이하의 정수이다. 둘째 줄부터 N개의 줄에는 1번부터 번호순서대로 각 원숭이에 대해 앙숙관계에 있는 원숭 www.acmicpc.net 신기한 그리디 문제다. 모든 원숭이를 한 우리에 모아두고 앙숙관계가 2마리 이상인 원숭이들을 다른 곳으로 옮겨놓는 방식으로하면 된다. i) 옮길 원숭이가 없다면 모든 원숭이에 대해 같은 우리에 앙숙관계인 원숭이가 1마리 이하임을 의미하므로 문제의 답을 찾을 수 있다. ii) 옮기는 경우가 있다면 옮기고 나서 앙숙관계인 원숭이가 1개 이상 줄어든다. 그러므로 이런 상황은 통틀어서 총 3n번까지 ..
2021.08.06 -
BOJ 2923 : 숫자 게임
https://www.acmicpc.net/problem/2923 문제에서 10)로 포인터들을 움직이면서 그리디하게 찾아주면 된다 코드
2021.08.06 -
BOJ 2437 : 저울
https://www.acmicpc.net/problem/2437 2437번: 저울 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓� www.acmicpc.net 이 문제는 코드는 아주 간단한데 왜 성립되는지 조금 생각해야 하는 문제이다. 일단 추를 정렬하자. 1부터 i까지의 합을 sum이라고 하자. (1 n; for(int i=0; i> a[i]; sort(a,a+n); ll sum=0; for(int i=0; i
2020.08.17