https://www.acmicpc.net/problem/1744
1744번: 수 묶기
길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에
www.acmicpc.net
풀이
수열의 합의 최대값을 구하는 문제이다. 숫자 2개를 위치에 관계 없이 묶거나 묶지 않고 더할 수 있으며, 묶을 경우엔 두 수를 곱해서 더해야 한다.
그냥 더하는 것보다 두 수를 곱할수록 합은 더 커진다. 그럼 어떻게 곱해야 더 크게 만들 수 있을까? 숫자 하나만 더한다고 생각했을 때, 가장 큰 수를 만드는 방법은 가장 큰 두 수를 곱하는 것이다. 즉, greedy하게 내림차순으로 큰 두 수씩 묶으면 값을 가장 크게 만들 수 있다.
음수인 경우엔 어떨까?
음수를 곱하면 양수가 되므로 마찬가지로 곱하는 게 항상 이득이다. 따라서, greedy하게 오름차순으로 절대값이 큰 두 수씩 묶으면 값을 가장 크게 만들 수 있다.
근데, 묶다가 마지막에 하나가 남는 경우가 생긴다. 양,음수 모두 홀수개일 때는 하나가 남는다.
음수의 경우 만약 0이 있다면 0과 곱하고, 0이 없다면 어쩔 수 없이 가장 작은 하나를 남겨둔다. 0을 곱하거나 양수와 곱하면 더 커질테니까.
양수는 남으면 그냥 더하는 수밖에 없다. 음수나 0이랑 곱하면 더 작이지기 때문이다.
즉, 0은 남는 음수에 곱하는 용도로 사용한다. 음수와 곱하면 음수를 더 크게 만들 수 있지만 음수는 음수끼리 곱하는 것이 더 이득이기 때문이다.
Greedy)
이 문제는 위와 같이 greedy 방식으로 풀면 해결할 수 있다. 근데 위 방법대로 하면 정답을 받지 못한다ㅋㅋ! 0과 음수는 예외처리 했지만 1은 고려해주지 않았기 때문이다.
1은 어떤 수를 곱해도 자기 자신이 된다. 하지만 더한다면? (자기자신+1)이 된다. 1은 0과 곱하면 0으로 더 작아지고, 음수와 곱해도 작아진다. 따라서 1은 항상 묶지 않고 따로 더해줘야 한다. 1은 모두 따로 빼서 더하고 나머지 양수에 위의 방법을 적용하면 정답을 받을 수 있다.
위 방법을 정리하면 다음과 같다.
1. 수열을 입력 받는다 - 양수,음수를 따로 저장해준다. 0이 있는지 체크하고, 1은 모두 빼서 정답에 미리 더해준다.
2. 양,음 수열을 각각 정렬한다.
3-1 양의 수열)
- 개수가 0이면 0을, 1개면 그 원소를 정답에 더한다.
- 짝수개라면 크기순으로 2개씩 묶어서 곱한 것을 합해서 정답에 더한다.
- 홀수개이면 가장 작은 수와 나머지 짝수개를 묶은 것을 합해서 정답에 더해준다.
3-2 음의 수열) 양의 수열과 절대값에 대해 같은 방식으로 처리해준다
4) 음의 수열이 홀수개 && 0이 수열에 있다면, 더해줬던 가장 큰 음수를 정답에서 빼준다.
코드
fun main(){
var answer = 0
val n = readLine()!!.toInt()
val negatives = mutableListOf<Int>()
val positives = mutableListOf<Int>()
var hasZero = false
repeat(n){ i ->
val number = readLine()!!.toInt()
when{
number == 0 -> hasZero = true // 여러 개여도 상관없다
number == 1 -> answer++ // 바로 더해준다
number > 1 -> positives.add(number)
else -> negatives.add(number)
}
}
val numOfNegative = negatives.size
val numOfPositive = positives.size
positives.sort()
negatives.sortDescending() // 같은 함수로 처리하기 위해 내림차순 정렬
// 3)
answer += handleSequence(positives, numOfPositive) + handleSequence(negatives, numOfNegative)
// 4)
if (numOfNegative % 2 != 0 && hasZero){
answer -= negatives[0]
}
println(answer)
}
fun handleSequence(sequence: MutableList<Int>, numOfSequence: Int): Int{
return when{
numOfSequence == 0 -> 0
numOfSequence == 1 -> sequence[0]
// 2개씩 묶어서 곱한 것을 모두 더한다.
numOfSequence % 2 == 0 -> sequence.chunked(2).map{ it[0]*it[1] }.reduce{ sum, num -> sum + num }
else -> sequence[0] +
sequence.subList(1, numOfSequence)
.chunked(2)
.map{it[0]*it[1]}
.reduce{sum, num -> sum + num}
}
}
리뷰
- 처음에 그리디 문제인지 몰랐다. 그리디 문제는 딱 보고 눈치챌 수 있을 거라고 생각했는데, 앞으로 열심히 풀어야겠다..ㅋㅋ
- 1도 예외처리를 해줘야 했다니. 숫자는 어렵다.
'Problem Solving > 백준' 카테고리의 다른 글
| (Kotlin) 백준 14501 - 퇴사 (0) | 2021.09.15 |
|---|---|
| (Kotlin) 백준 1904 - 01타일 (0) | 2021.09.14 |
| (Kotlin) 백준 1707 - 이분 그래프 (0) | 2021.09.01 |
| (Kotlin) 백준 1062 - 가르침 (0) | 2021.08.31 |
| (Kotlin) 백준 18427 - 함께 블록 쌓기 (0) | 2021.08.30 |