백준/그리디 (26) 썸네일형 리스트형 [ICPC] 백준 11497 - 통나무 건너뛰기 www.acmicpc.net/problem/11497 풀이 가장 높은 통나무를 가운데 세운다! 짝수개면 상위 2개 통나무를 가운데 세운다! 그리고 남은 통나무들을 내림차순으로 양 옆으로 배치해나가면 원형을 고려했을 때의 최적해를 구할 수 있다! 양 옆에 통나무를 놓을 때 발생하는 높이차가 더 적은 경우로 배치하여 최적 부분 구조가 깨지지 않도록 하자! 구현 통나무를 양 옆에 붙이는 행위를 덱으로 구현하였다. 전체 코드 더보기 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 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56.. 백준 12845 - 모두의 마블 www.acmicpc.net/problem/12845 가치가 가장 큰 카드가 인접한 카드들을 잠식해나가면 최대 골드를 얻게 된다. 가치가 가장 큰 카드를 찾고 나머지 카드들을 문제 조건에 맞게 모두 더해주자. 전체 코드 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 #include using namespace std; int ar[1000]; int n; int res; int main() { cin.tie(0); ios::sync_with_stdio(false); cin >> n; for (int i = 0; i > ar[i]; sort(ar, ar + n); for (int i = n - 2; i >= 0; --i) res += ar[n - 1] +.. [KOI] 백준 2437 - 저울 www.acmicpc.net/problem/2437 예제에 주어진 추들을 정렬하고 무게들을 더하다 보면 무게가 30인 추를 넣을 때 지금까지 더한 무게 20과 거기에 30을 더한 무게 50 사이의 무게를 만들 방법이 없어 답은 21이 되는 것을 관찰할 수 있다. 즉 정렬된 추들의 무게를 누적 합으로 저장하면서 현재 추가할 추의 무게가 누적 합 범위 안에 들어온다면 누적합에서 현재 추를 더한 범위 내의 무게를 만들 수 있다고 생각할 수 있다. 그렇지 않다면, 즉 추가할 추의 무게가 누적 합 + 1 범위를 벗어난다면 답은 지금까지 더한 누적 합 + 1이 된다. 왜 누적 합 + 1이냐면 추가할 추의 무게가 누적 합 + 1일 경우 누적 합 + 1은 추가할 추 한개로 무게를 잴 수 있기 때문에 그보다 큰 범위를 .. [ICPC] 백준 1700 - 멀티탭 스케줄링 www.acmicpc.net/problem/1700 풀이 정해는 OS분야에서 고안되었으나 사용하지 못하는 최적 페이지 교체 알고리즘이다. 멀티탭이 가득 찼을 때 꽃힌 전기용품 중에서 가장 늦게 사용될 물건을 빼버린다는 것인데 이 말은 전체에서 마지막으로 나타나는 전기용품이 아니라 다음에 쓸 전기용품 중 처음으로 등장했을 때 그 순서가 가장 늦은 용품을 빼는 것이다. 물론 더이상 쓰지 않을 물건은 최우선으로 빼줘야 한다. 구현 어떤 용품의 사용횟수가 얼마나 남았는지 mp배열로 저장해준다. 멀티탭에 어떤 용품이 꽃혔는지 셋으로 관리하면서 멀티탭이 가득차지 않았거나 꽃혔던 물건을 사용한다면 해당 용품을 셋에 삽입하여 넘어간다. 플러그를 뽑아야만 한다면 먼저 사용을 다 한 물건이 있는지 확인해주고 그렇지 않다면.. [COCI] 백준 9935 - 문자열 폭발 icpc.me/9935 받은 문자열 s를 반복문을 통해 스트링 a에 한글자씩 넣어주자. a에 넣은 마지막 글자가 터트려야 할 문자열 b의 마지막 문자와 일치하는지 확인한다. 일치하지 않는다면 반복문을 계속하면 되고, 일치한다면 a의 마지막부터 검색하여 a의 끝부분이 b와 일치하는지 확인한다. 만약 문자열이 일치한다면 그만큼 터트리고 반복문을 진행시키면 된다. 이 과정을 반복해서 나온 a가 답이 된다. a의 길이가 0이면 FRULA를 출력해주자. 전체 코드 더보기 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 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 #include.. 이전 1 2 3 4 5 6 다음
