본문 바로가기
반응형

그리디2

[cpp 알고리즘] 백준 1744 수 묶기 [백준] 1744 수 묶기 풀이 그리디 알고리즘, 정렬, 많은 조건 분기 문제 출처: https://www.acmicpc.net/problem/1744 문제 요약 - 길이가 N인 수열이 주어졌을 때, 두 수를 곱하거나 그대로 둘 수 있다. 이 수들을 모두 더한 값들 중 최댓값을 구하면 된다. 풀이 정리 1. 일단 오름차순으로 정렬한다. 2. 숫자 1을 기준으로 3가지 경우로 나뉘어진다. (1) 1보다 작은, 0이거나 음수인 경우 -> 앞쪽(작은 수)부터 두 수를 곱해서 최종 결과 값에 더하면 된다. (2) 1인 경우 -> 곱하는 데 사용하지 않고, 더하면 된다. (3) 1보다 큰 양수인 경우 -> 뒤쪽(큰 수)부터 두 수를 곱해서 최종 결과 값에 더하면 된다. 3. (1)의 경우 혹은 (3)의 경우가 홀.. 2023. 11. 11.
[cpp 알고리즘] 백준 25943 양팔저울 [백준] 25943 양팔저울 cpp 풀이 2022 ICPC KOREA 인터넷 예선(Internet Competition) A번 구현, 그리디 알고리즘 https://www.acmicpc.net/problem/25943 문제 요약 - n개의 자갈이 순서대로 주어지고, 아래 두 가지 규칙을 고려하여 양팔저울에 올리면 된다. (1) 평형인 경우, 자갈을 양팔저울의 왼쪽에 올려둔다. (2) 평형이 아닌 경우, 양팔저울의 가벼운 쪽에 저울을 올려둔다. - 최종적으로 양팔 저울의 평형을 맞추면 된다. 이 때는 1g, 2g, 5g, 10g, 20g, 50g, 100g의 7종류의 무게추를 사용하는데, 이 때 무게추의 최소 개수를 구하면 된다. 풀이 정리 1. 자갈 N개의 개수만큼 반복문을 돌면서, 좌/우 중에 어디 두.. 2023. 9. 27.
반응형

티스토리툴바