[백준 1029] - 그림 교환(Kotlin)[골드1]

문제

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

1029번: 그림 교환

 

문제 풀이

문제를 보고 감이 안 잡혀서 알고리즘 분류를 보고 풀 수 있었던 문제였다.

비트마스킹이 왜 필요한가에 대해서 생각을 하다가, 저번에 풀었던 외판원 순회 문제가 떠올랐다.

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

2098번: 외판원 순회

해당 문제와 비슷한 문제인것 같다.

 

우선 n의 범위가 2부터 15까지라서 완전탐색을 해서 모든 경우의 수를 계산하려고 했지만, 현재 작품을 산 사람과, 다음에 작품을 산 사람들을 모두 고려해야 하는 순열을 구해야 했기 때문에 최대 15! 경우의 수가 나왔고, 시간초과를 피할 수 없다고 생각했다.

 

다음 방법으로는 백트래킹도 고려를 해봤는데, 가지치기에 대한 조건이 현재 사람에 대해 더이상 그림을 살 수 있는 사람이 없을 경우가 조건일 것 같았다. 그러할 경우 더 이상의 탐색은 무의미하기 때문이다.

하지만 문제에서의 그림을 살 수 있는 조건은 크거나 같은 가격이기 때문에 모든 사람의 매입가가 같다면 가지치기에 대한 효율이 그리 높지 않을것이라고 생각했다.

 

그렇다면 탐색을 더 깊게 하지 않기 위해선 이전의 정보가 있다면 그것을 그대로 반환하는 메모이제이션이 좋다는 생각이 들었다.

그러기 위해서 DP 테이블을 어떻게 세우는지가 중요했다.

 

우선 처음으로 고려해야할 것은 현재까지 몇 명이 그림을 샀는지였다.

 

현재 내가 탐색하려는 단계에서의 그림을 산 사람이 누구인지 알아야, 중복된 거래가 발생하지 않는다.

여기서 그림을 산 사람에 대한 정보를 비트마스킹을 통해서 저장한다.

이와 비슷하게 위에서 언급했던 문제도, TSP 문제에서 현재까지 방문했던 도시들을 비트마스킹을 통해서 방문처리를 한다.

 

비트마스킹에 대한 처리는 간단하다.

 

첫번째 사람이 샀다면 1<<1, 두 번째 사람이 샀다면 1<<2, n번째 사람이 샀다면 1<<n과 같이 연산을 진행한다.

예를 들어,

첫번째 사람이 샀다면 해당 방문의 값은 1일 것이다.

그리고 첫 번째 사람과 두 번째 사람 모두 샀다면 방문의 값은 11 -> 3일 것이다.

이렇게 우리는 누가 샀는지에 대한 정보를 비트마스킹을 통해서 1로 채울 것이다.

사람의 수는 최대 15명이기 때문에 메모리상으로 굉장히 넉넉하다. 최대 2^15이기 때문이다.

 

이렇게 방문을 처리했다면, 어떠한 사람이 그림을 샀는지에 대한 처리를 해야 한다.

위에서 말한 것처럼 첫 번째 사람이 그림을 사면 1, 두 번째 사람이 그림을 산다면 2, n번째 사람이 산다면 2^n일 것이다.

이 정보를 현재 방문정보와 and 연산을 해서 1이 아니라면 해당 사람은 그림을 사지 않았다는 뜻이다.

현재 내 방문 정보가 3이라면 11이다. 만약 세 번째 사람이 그림을 샀는지에 대한 검사를 한다고 가정하자.

11과 100 (2<<3) and 연산을 한다고 하면 답은 0이 될 것이다.

이렇게 그림을 샀는지에 대한 처리를 할 수 있다.

 

다음으로 고려해야 할 것은 마지막으로 산 가격이다.

당연하게도 그림을 사야 하는 조건이 그림을 산 가격보다 크거나 같아야 하기 때문에 해당 정보는 반드시 필요하다.

 

하지만 이렇게 2개의 정보만으로 DP 테이블을 구성하기에는 조금 부족했다.

왜냐하면 마지막 가격만을 가지고, 현재 그림을 산 사람에 대한 정보를 판단하기에는 무리가 있기 때문이다.

마지막 가격으로 그림을 살 수 있는지를 판단할 수 있지만, 어떤 사람이 그림을 사야 하는지를 구해내기엔 부족하기 때문이다.

 

따라서  (현재 그림을 산 사람들), (현재 그림을 들고 있는 사람), (마지막으로 그림이 거래된 가격) 3개의 정보로 DP 테이블을 구성했다.

DP 테이블의 값은 그림을 산 사람의 수이다.

 

이렇게 DP 테이블을 세웠다면, 다음은 완전탐색과 유사하다.

그 과정에서 메모이제이 션만 섞어준다면 끝이다.

 

 

전체 코드

import kotlin.math.max

class Solution {

    private val br = System.`in`.bufferedReader()
    private var n = 0
    private lateinit var ary: Array<IntArray>
    private lateinit var dp: Array<Array<IntArray>>
    fun run() {
        input()
        print(solve(1,0,1,0))
    }

    private fun input() {
        n = br.readLine().toInt()
        ary = Array(n) { IntArray(n) }
        for (i in 0 until n) {
            val line = br.readLine()
            for (j in 0 until n) {
                ary[i][j] = line[j].toString().toInt()
            }
        }
        dp = Array(1 shl n) { Array(n) { IntArray(10) } }
    }

    private fun solve(visited: Int, curPeople: Int, depth: Int, lastPrice: Int): Int {

        if (visited == 1 shr n - 1) { //다 방문했을 경우
            return 0
        }

        if (dp[visited][curPeople][lastPrice] != 0) {
            return dp[visited][curPeople][lastPrice]
        }

        dp[visited][curPeople][lastPrice] = depth

        for (i in 0 until n) {
            val next = 1 shl i
            val nowPrice = ary[curPeople][i]
            if (visited and next != 0) { //이미 산 사람이라면
                continue
            }
            if (lastPrice > nowPrice) { //마지막에 산 가격보다 크다면
                continue
            }
            dp[visited][curPeople][lastPrice] = max(dp[visited][curPeople][lastPrice],solve(visited or next, i, depth + 1, nowPrice))
        }
        return dp[visited][curPeople][lastPrice]
    }
}

fun main() {
    val solution = Solution().run()
}