[백준] (Swift) 1744번 - 수 묶기 (골드4, 그리디)

 

⚫️ 문제

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

1744번: 수 묶기

 

⚫️ 나의 풀이

풀이 방식은 바로 생각났다. 핵심은 -는 -끼리 곱했을 때 양수가 되고, 0이 입력되는 경우 minus인 수랑 곱해주면 개이득이라는 사실!

• input을 minus와 0, plus로 나눠서 받았고, 배열을 따로 만들어주었다.
• 우선 수를 곱해주는게 그냥 더해주는 것보다는 훨씬 이득이다. 그러므로, 주어진 input의 개수가 홀수인 경우, 큰수들은 묶어서 최대 수로 만들어주고 제일 작은수만 단일로 더해주자.
• minus는 그 반대, 제일 작은수 두개를 묶어서 최대양수로 만들어주고, 만약 홀수인경우 제일 큰수를 그냥 단일로 더해주자.

이 과정을 그대로 코드로 만들어주면 ? 아래와 같은 코드가 나온다.

❌ 1차시도 - 틀렸습니다.

import Foundation

private func solution() -> Int {
    let n = Int(readLine()!)!
    var minusNums = [Int]()
    var plusNums = [Int]()

    for _ in 0..<n {
        let input = Int(readLine()!)!
        // 0 이면 마이너스랑 곱해주는게 개이득
        if input <= 0 {
            minusNums.append(input)
        } else {
            plusNums.append(input)
        }
    }

    var sum = 0
    minusNums = minusNums.sorted(by: <)
    plusNums = plusNums.sorted(by: >)

    var idx = 0
    while idx < minusNums.count {
        if idx + 1 < minusNums.count {
            sum += minusNums[idx] * minusNums[idx+1]
        } else if idx + 1 >= minusNums.count {
            sum += minusNums[idx]
        }

        idx += 2
    }

    idx = 0
    while idx < plusNums.count {
        if idx + 1 < plusNums.count {
            sum += plusNums[idx] * plusNums[idx+1]
        } else if idx + 1 >= plusNums.count {
            sum += plusNums[idx]
        }

        idx += 2
    }

    return sum
}

print(solution())

흠,, 틀렸다. 원하는 답이 출력되지 않는 모양이다. 

다음날...  2차시도 - 맞았습니다!

아니 이전에 공주님 문제도 그랬듯, 코딩테스트가 안풀리고 답답하고 모르겠으면 다음날 푸는것도 하나의 방법인것같다. 문제에 대한 고민을 깊게한 터라 문제를 까먹진 않을테고, 조금 더 머리가 가벼워진 상태에서 생각할 수 있기 때문?? 이렇게 문제 안풀리면 앞으로 다음날로 미뤄봐야겠다 ^0^/

그래서 이번 문제도 보자마자 틀린 부분을 바로 파악했다. 0은 마이너스달린 놈에게 곱해주면 0이 되어버려서 이득이다. 하지만 1은? 1은 수를 묶어주기보다는, 따로 더해주는게 가장 최대의 값으로 만들 수 있다. 따라서,,,, 현재 내가 그냥 써놨던 코드는 1도 모두 곱해주는 구조로 되어있기 때문에, 오답이었던 것이다. 지금 내가 써놨던 풀이를 그대로 유지하고, 추가로 1을 따로 처리해주면서 더해주면 최대를 구할 수 있다. 

import Foundation

private func solution() -> Int {
    let n = Int(readLine()!)!
    var minusNums = [Int]()
    var plusNums = [Int]()
    var ones = [Int]()

    for _ in 0..<n {
        let input = Int(readLine()!)!
        // 0 이면 마이너스랑 곱해주는게 개이득
        if input <= 0 {
            minusNums.append(input)
        } else if input == 1 {
        // 1은 그냥 더해주는게 개이득
            ones.append(input)
        } else {
            plusNums.append(input)
        }
    }

    var sum = 0
    minusNums = minusNums.sorted(by: <)
    plusNums = plusNums.sorted(by: >)

    // minus 처리
    var idx = 0
    while idx < minusNums.count {
        if idx + 1 < minusNums.count {
            sum += minusNums[idx] * minusNums[idx+1]
        } else if idx + 1 >= minusNums.count {
            sum += minusNums[idx]
        }

        idx += 2
    }

    // plus 처리
    idx = 0
    while idx < plusNums.count {
        if idx + 1 < plusNums.count {
            sum += plusNums[idx] * plusNums[idx+1]
        } else if idx + 1 >= plusNums.count {
            sum += plusNums[idx]
        }

        idx += 2
    }
    
    // 1은 따로 더해주기~
    return sum + ones.count
}

print(solution())

 

 

우아아~~ 비교적 간단하게 골드 문제 해결!