반응형
https://www.acmicpc.net/problem/1744
1744번: 수 묶기
길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에
www.acmicpc.net
소스코드
풀이
최적의 해를 구하는 그리디 알고리즘 문제이며, 입력으로 받는 수들을 양수, 음수, 0, 1로 나눠서 어떻게 연산을 해줄지에 대해 생각해야 하는 문제입니다.
1. 양수는 큰 수부터 두개씩 곱해야지만 가장 큰 수가 나온다 ( 정렬 시 내림차순 정렬)
ex) 5,4,3,2,1
2. 음수는 작은 수부터 두개씩 곱해야지만 가장 큰 수가 나온다 ( 정렬 시 오름차순 정렬)
ex) -5,-4,-3,-2,-1
3. 1은 무조건 더해주는 것이 결과값을 가장 크게 만든다.
4. 0을 처리하기 위해선 음수 배열의 가장 마지막에 있는 수와 곱해준다. ( 0만 남으면 자동으로 결과값에 '+')
이러한 방식으로 수를 분리한 뒤, 0부터 배열의 길이까지 2개씩 증가하는 반복문을 사용하여,
수가 2개 남아있다면 두 수를 곱한 뒤 결과값에 더해주고, 수가 하나만 남아있다면 바로 결과값에 더해줍니다 !
반응형
'Algorithm > 백준' 카테고리의 다른 글
| [백준 알고리즘] 2941번: 크로아티아 알파벳 (Python) (0) | 2023.03.28 |
|---|---|
| [백준 알고리즘] 11718번: 그대로 출력하기 (Python) (0) | 2023.03.24 |
| [백준 알고리즘] 1316번: 그룹 단어 체커 (Python) (0) | 2023.03.22 |
| [백준 알고리즘] 1181번: 단어 정렬 (Python) (0) | 2023.03.21 |
| [백준 알고리즘] 1158번: 요세푸스 문제 (Python) (0) | 2023.03.21 |