[Swift Algorithm] 수 묶기 BOJ #1744

문제 설명

길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 상관없이 묶을 수 있다. 하지만, 같은 위치에 있는 수(자기 자신)를 묶는 것은 불가능하다. 그리고 어떤 수를 묶게 되면, 수열의 합을 구할 때 묶은 수는 서로 곱한 후에 더한다.

예를 들면, 어떤 수열이 {0, 1, 2, 4, 3, 5}일 때, 그냥 이 수열의 합을 구하면 0+1+2+4+3+5 = 15이다. 하지만, 2와 3을 묶고, 4와 5를 묶게 되면, 0+1+(2*3)+(4*5) = 27이 되어 최대가 된다.

수열의 모든 수는 단 한번만 묶거나, 아니면 묶지 않아야한다.

수열이 주어졌을 때, 수열의 각 수를 적절히 묶었을 때, 그 합이 최대가 되게 하는 프로그램을 작성하시오.

 

입력

첫째 줄에 수열의 크기 N이 주어진다. N은 10,000보다 작은 자연수이다. 둘째 줄부터 N개의 줄에, 수열의 각 수가 주어진다. 수열의 수는 -10,000보다 크거나 같고, 10,000보다 작거나 같은 정수이다.

 

출력

수를 합이 최대가 나오게 묶었을 때 합을 출력한다. 정답은 항상 231보다 작다.

 

입출력 예제

입력

4
-1
2
1
3

출력

6

 

내 문제 풀이

import Foundation

let N = Int(readLine()!)!
var minus = [Int]()
var plus = [Int]()
var answer = 0

for _ in 0..<N {
    let input = Int(readLine()!)!
    if input <= 0 { minus.append(input) } // 음수
    else if input == 1 { answer += 1 } // 1일 경우 바로 answer에 누적
    else { plus.append(input) } // 양수
}

plus.sort(by: >)
minus.sort(by: <)

if minus.count % 2 == 1 { answer += minus.removeLast() }
if plus.count % 2 == 1 { answer += plus.removeLast() }

while minus.count > 0 || plus.count > 0 {
    if minus.count > 0 { answer += minus.removeLast() * minus.removeLast() }
    if plus.count > 0 { answer += plus.removeLast() * plus.removeLast() }
}

print(answer)

👉 곱했을 때 이득이 되는 수를 찾고, 더했을 때 이득이 되는 수가 무엇인지 정확히 파악하는 것이 핵심!

이 문제는 음수부터 양수까지 모두 다루기 때문에 음수일 경우, 0, 1일 경우, 그리고 양수일 경우를 각각 고려해야한다.

그리고 또 하나 고려할 점은, 양수든 음수든 최대한 절댓값이 큰 수끼리 곱해주는 것이 득이 된다는 것.

그러면 이제 위의 전제를 토대로 우리가 처리할 사항들을 정리해보자.

1) 0이하의 수(0과 음수)는 절댓값이 큰 수부터 차례로 곱해주는 것이 득이다.

2) 1은 몇 개가 됐든 더해주는 것이 득이다.

3) 2이상의 양수는 큰 수부터 차례로 곱해주는 것이 득이다.

• 위의 사항들을 전제로 문제를 풀이하기 위해, 수를 입력받을 때 (0 이하 / 1 / 2 이상) 으로 나누어 받았다.
  1의 경우에는 어차피 더하기만 할 것이기 때문에, 바로 answer에 1씩 더해주었다.
  그리고 0 이하의 수는 minus 배열, 2 이상의 수는 plus 배열에 각각 담아주었다.
• plus 및 minus 배열에 담긴 수들은 절댓값이 큰 수끼리 곱해줄 예정이기에 알맞게 정렬해주었다.
  하지만 아무리 plus, minus 배열에 담긴 수들이 곱했을 때 득이 되는 수일지라도,
  각 배열에 담긴 수의 개수가 홀수일 경우에는 곱해질 수 없는 수가 존재하기 때문에
  그 때는 제일 작은 수를 그냥 더해주기 위해서 절댓값 기준 작은 수가 뒤로 가도록 정렬한다.
• 나머지 연산으로 plus, minus 배열의 요소 개수를 확인하여 홀수일 경우에는
  answer에 각 배열의 마지막 요소를 삭제함과 동시에 값을 누적해주었다.
• minus와 plus 배열 모두 뒤에서부터 두 개씩 곱해 answer에 누적하는 방식으로 연산했다.

 

💡 피드백

• 풀이 전, 먼저 어떤 수는 곱해야 하고 어떤 수는 더해야할지 미리 고려한 후에 코드를 작성하니 쉽게 풀 수 있었다.

 

---

 

문제

https://www.acmicpc.net/problem/1744