개발해요

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

풀이

길이가 (k-1)인 계단 수에 마지막 자리 숫자의 +1, -1한 수를 붙이면 길이가 k인 계단 수를 구할 수 있다.

ex) 12 -> 121, 123

이걸 점화식으로 표현하기 위해 dp[k][i]를 아래와 같이 정의하면,

dp[k][i]: 길이가 k이고, 마지막 자리 숫자가 i인 계단 수의 개수

dp[k][i] = {

               if (i == 0), dp[k-1][i+1]

               if (0 < i < 9), sum(dp[k-1][i+1]) + sum(dp[k-1][i-1])

               if (i == 9), dp[k-1][i-1]

             }

ex) 길이가 4이고 3으로 끝나는 계단 수의 개수는, 길이가 3이고 2로 끝나는 계단 수의 개수와 4로 끝나는 계단 수의 개수를 합한 값

위와 같이 계단 수의 길이를 기준으로 이전 항의 값으로 다음 항의 값을 표현할 수 있고, 키 포인트는 이전 길이의 계단 수들이 어떤 숫자로 끝났는지 기록하는 것이다. 그리고 0과 9로 끝나는 수들은 다른 숫자들과는 다르게 1과 8에서만 파생된다.

이 문제는 다이나믹 프로그래밍 유형으로, 문제 상황을 이전 값으로 다음 값을 표현할 수 있으면 해결이 가능하다. 그걸 어떻게 생각해내느냐는 어릴 때 수학을 열심히 했거나, 머리가 좋거나, 둘 다 아니라면 문제를 많이 풀어보는 수밖에 없는듯 하다.

코드

fun main(){
    val n = readLine()!!.toInt()
    var table = Array(100){IntArray(10)}

    // 한 자리 계단 수는 1~9 한 개씩
    for (i in 1..9){
        table[0][i] = 1
    }
    
    // 길이 2~n까지 n-1번 반복
    repeat(n-1){ k ->
        table[k+1][0] = table[k][1]
        table[k+1][9] = table[k][8]

        for (i in 1..8){
            table[k+1][i] = (table[k][i-1] + table[k][i+1]) % 1_000_000_000
        }
    }

    // 길이 n의 모든 계단 수의 개수를 합한다
    println(table[n-1].toList().reduce{acc, num -> (acc + num) % 1_000_000_000})
}

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/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도 예외처리를 해줘야 했다니. 숫자는 어렵다.

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

풀이

그래프의 모든 노드를 인접한 노드와 같은 집합에 속하지 않도록 하면서, 두 집합으로 분할할 수 있는지 판별하는 문제이다.

먼저 노드를 두 집합으로 분할해야 하므로, 모든 노드를 방문하면서 어떤 집합에 속할 것인지를 정해준다. 분할하는 것을 쉽게 색칠한다고 표현하자. DFS나 BFS를 사용해서 노드를 한번씩만 방문하면서 인접 노드를 현재 노드와 다른 색으로 색칠하면 된다. 나는 colors라는 배열을 만들어서 모든 노드를 0과1로 나누었다. 

얼핏 단순하게 "인접 노드를 모두 다른 색으로 칠하면 무조건 이분 그래프로 만들 수 있는 거 아닌가?"라고 생각할 수도 있지만, 인접노드가 이미 이전에 방문되었고, 현재 노드와 같은 색으로 칠해진 경우가 발생할 수 있다.

분할이 끝나면 그래프에서 모든 노드를 돌면서 자신과 같은 색인 인접노드가 있는지 확인해주면 이분 그래프인지 아닌지 판별할 수 있다.

참고로 연결 그래프라면 DFS나 BFS를 사용해서 노드를 한번씩만 방문하면서 이분 그래프 여부를 판별할 수 있으며, 연결 그래프가 아니라면 위에 언급한 대로 노드마다 인접 노드를 검사해주면 된다.

이를 좀 더 구체적으로 적으면 다음과 같다.  

1. DFSorBFS를 사용해서 모든 노드를 한번씩 방문한다.

2. 노드마다 인접 노드와 다른 색으로 칠해준다. 

3. 노드마다 인접 노드를 확인해서 같은 색으로 칠한 노드가 있으면 "NO", 없으면 "YES"를 출력한다.

코드

fun main(){
    for(i in 0 until readLine()!!.toInt()){
        var numberOfNode = 0
        var numberOfEdge = 0
        readLine()!!.split(" ").let{
            numberOfNode = it[0].toInt()
            numberOfEdge = it[1].toInt()
        }

        val visit = Array(numberOfNode){false}
        val colors = Array(numberOfNode){-1}
        val graph = Array(numberOfNode){mutableListOf<Int>()}
        // 인접리스트로 그래프 저장
        for(i in 0 until numberOfEdge){
            readLine()!!.split(" ").map{it.toInt()-1}.let{
                graph[it[0]].add(it[1])
                graph[it[1]].add(it[0])
            }
        }

	// DFS로 모든 노드 방문
        (0 until numberOfNode).forEach { node ->
            if (!visit[node]){
                visit[node] = true
                colors[node] = 0	// 첫 노드를 0으로 색칠
                dfs(graph, node, visit, colors)
            }
        }

	// 모든 노드마다 인접 노드가 무슨 색인지 확인한다
        if (isBipartite(graph, colors)){
            println("YES")
            continue
        }
        println("NO")
    }
}

fun isBipartite(graph: Array<MutableList<Int>>, colors: Array<Int>): Boolean{
    graph.indices.forEach { node ->
        graph[node].forEach { adjacent ->
            if (colors[node] == colors[adjacent]){	// 현재 노드와 인접노드의 색이 같으면 false
                return false
            }
        }
    }

    return true
}

fun dfs(graph: Array<MutableList<Int>>, node: Int, visit: Array<Boolean>, colors: Array<Int>){
    graph[node].forEach { toNode ->
        if (!visit[toNode]){
            visit[toNode] = true
            colors[toNode] = (colors[node]+1) % 2	// 인접노드를 현재 노드와 다른 색(0,1)으로 칠한다
            dfs(graph, toNode, visit, colors)
        }
    }
}

리뷰

이분그래프에 대해 알고 있고, DFS와 BFS를 쓸 줄 아는지 묻는 문제였던 것 같다.