[백준] 5557번 1학년

5557번 1학년

접근 방법

DFS, BFS를 사용할 경우 예제만 보더라도 70억개를 확인해야한다. 따라서 다른 방법을 고려하였다

다른 방법으로 DP를 떠올렸고 상근이는 (0..20)까지의 숫자만 알고 있으므로 크기가 21인 Array를 이용하여 해당 값이 나온 횟수를 이용해서 문제를 풀 수 있었다.

하지만 Array가 바로 생각나지 않고 Map 방식이 떠올라서 <Key, Count> 값을 갖는 Map을 이용해서 풀었고, 해당 문제에서는 이전 배열과 현재 배열만 값이 있으면 되므로 map 1개와 임시 map 1개를 이용하여 풀었다.

하지만 2차원 배열을 이용해서 푸는 방법도 있고, 배열 2개 혹은 2차원 배열의 row가 2개인 것을 이용하면 된다

시간 복잡도

O(21 * n)이므로 O(n)

Code

import java.io.BufferedReader
import java.io.InputStreamReader

class StandardIO {
    private val br = BufferedReader(InputStreamReader(System.`in`))
    
    fun getIntFromBr(): Int {
        return br.readLine().toInt()
    }
    
    fun getNumListFromBr(): List<Int> {
        return br.readLine().split(" ").map { it.toInt() }
    }
}

fun main() {
    val io = StandardIO()
    val n = io.getIntFromBr()
    val numList = io.getNumListFromBr()
    
    val target = numList.last()
    var map = hashMapOf<Int, Long>().apply {
        put(numList.first(), 1)
    }
    numList.subList(1, numList.size -1).forEach { num ->
        val tmpMap = hashMapOf<Int, Long>()
        map.keys.forEach { key ->
            val plus = key + num
            val minus = key - num
            if (plus in 0..20) {
                if (tmpMap.containsKey(plus)) {
                    tmpMap.replace(plus, tmpMap[plus]!! + map[key]!!)
                } else {
                    tmpMap[plus] = map[key]!!
                }
            }
            if (minus in 0..20) {
                if (tmpMap.containsKey(minus)) {
                    tmpMap.replace(minus, tmpMap[minus]!! + map[key]!!)
                } else {
                    tmpMap[minus] = map[key]!!
                }
            }
        }
        map = tmpMap
    }
    val count = map.getOrDefault(target, 0)
    println("$count")
}