개발해요

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

문제유형: DP

접근 방법

DP 문제라는 걸 알고 접근했는데 처음에 해결법이 떠오르지 않았다. 여러 블로그를 참고해서 이해했는데, 그것을 토대로 생각해낸 접근법은 다음과 같다.

상담을 하는데 필요한 기간은 1일보다 클 수 있기 때문에, 모든 상담을 할 수는 없다. 예를 들어서 1일에 상담을 하게 되면, 2일, 3일에 있는 상담은 할 수 없게 된다. 2일에 있는 상담을 하게 되면, 3, 4, 5, 6일에 잡혀있는 상담은 할 수 없다. 또한, N+1일째에는 회사에 없기 때문에, 6, 7일에 있는 상담을 할 수 없다.

위의 문제 지문에서 힌트를 얻을 수 있는데, 특정 날짜에 상담을 하느냐 안하느냐에 따라 결과가 달라진다.

a[i]의 의미를 i일부터 n일까지 얻을 수 있는 이익이라고 정의한다면, 경우의 수를 2가지로 나눌 수 있다.

1. i일에 일을 안하는 경우
2. i일에 반드시 일을 반드시 하는 경우.

점화식 :  price[i] = max( price[i+1], price[i] + price[ i + time[i] ] )

• if ( n+1 < i + time[i] ) -> price[i] = price[i+1]: 해당 날짜에 상담했을 때 제때 퇴사할 수 없다면, 그 날짜엔 일을 하지 않는다.  

n = 7이고 T[7] = 1일 때 (i + time[i]) = 8 > 7이지만, 7일에도 상담이 가능하다.

따라서, 배열 크기를 n+2, 초기값 price[n+1] = 0으로 초기화 해주면 i = n부터 반복문을 시작할 수 있다.

코드

fun main(){
    val n = readLine()!!.toInt()
    val time = IntArray(n+2)
    val price = IntArray(n+2)

    for (i in 1..n){
        val numbers = readLine()!!.split(" ").map{ it.toInt() }
        time[i] = numbers[0]
        price[i] = numbers[1]
    }
    price[n+1] = 0	// 초기값

    for (i in n downTo 1){
        if ( n+1 < i + time[i] ){	// 예외처리
            price[i] = price[i+1]
            continue
        }

        price[i] = max(price[i+1], price[i] + price[ i + time[i] ])	// 점화식
    }

    println(price[1])
}

리뷰

• dp 기분 문제였지만 해결법을 떠올리고, 풀이를 이해하는 게 쉽지 않았다.
• 바텀업 방식을 하향식으로 생각해볼 수도 있구나.
• 꾸준히 풀어서 익숙해져야지.

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

풀이)

사용할 수 있는 타일은 (1, 00) 2가지이다.

아마 모든 경우의 수를 생각해서 조건문으로 문제를 풀려고 하면 머리가 터질 것이다.

다이나믹 프로그래밍)

사실 이 문제는 다이나믹 프로그래밍으로 유명한 기본 문제인데, 나 역시 DP를 공부하려고 푼 문제다!ㅎㅎ

DP의 핵심 개념은 크게 2가지이다. 

1. 재귀적으로 생각한다. 즉, 작은 문제의 정답은 이미 구해졌다고 믿는다.

2. 불필요한 계산을 줄인다.

(서울대생 분께서 아주 친절하게 설명해주십니다: https://www.youtube.com/watch?v=2RwlzBDhGh4)

1번의 재귀적으로 생각한다는 것은 점화식을 구하는 것과 같다.

타일의 개수는 1)마지막에 반드시 1을 사용하는 경우와 2)반드시 00을 사용하는 경우 2가지로 나눌 수 있는데, 이게 모든 경우의 수를 커버한다.

이것을 점화식으로 표현하면, a(n) = a(n-1) + a(n-2), 초기값은 a(1) = 1, a(2) = 2이 되는데,

a(n)은 타일의 개수가 n일 때, 만들 수 있는 모든 2진수의 가짓수를 의미한다.

피보나치랑 같은 식이 나와서 뭐지? 싶었는데 어이없게도 이게 맞다.

2번의 불필요한 계산을 줄이는 건, 탑다운 방식으로 풀 때는 메모이제이션 방식을, 바텀업 방식에서는 배열에 값을 저장해서 같은 문제의 답을 다시 구하지 않도록 해주면 된다.

이제 이것을 코드로 작성하면 놀랍도록 짧은 코드가 나오게 된다.

코드)

fun main(){
    val n = readLine()!!.toInt()
    val dp = IntArray(1_000_001)	// 크기 n+1로 설정하면, n=1일 때 인덱스 에러 생겨요ㅠㅠ
    dp[1] = 1; dp[2] = 2

    for (i in 3..n){
        dp[i] = (dp[i-2] + dp[i-1]) % 15746 // 점화식
    }
    
    println(dp[n])
}

리뷰)

• 처음에 배열 크기를 n+1로 하면, n=1일 때 인덱스 에러로 틀릴 수 있다.
• 맞아요 그게 저에요.

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

풀이

수열의 합의 최대값을 구하는 문제이다. 숫자 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도 예외처리를 해줘야 했다니. 숫자는 어렵다.