[백준 2629] - 양팔저울(Kotlin)[골드3]

문제

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

2629번: 양팔저울

 

문제 풀이

골드 3이라는 난이도 치고는 접근방법을 빨리 생각해 낸 문제였던 거 같다.

배낭문제와 비슷하다고 생각하고 접근했었는데, 문제를 풀고 다른사람의 풀이과정을 보니 다들 배낭과 비슷하다고 생각했던 것 같다.

그 정도로 접근하기가 쉬웠던 문제였던것 같다.

추를 사용해서 만들 수 있는 모든 무게를 검사해 주면 된다.

추를 사용해서 만들 수 있는 무게에 대한 방법은 크게 3가지 방법이 있을 것이다.

추 그대로의 무게, 두 개의 추를 더한 무게, 뺀 무게가 될 것이다.

우선 나는 DP 배열을 2차원 배열로 선언했다.

DP [i][j] = i개의 추를 사용해서 j 무게를 만들 수 있는지에 대한 여부

위의 3가지 방법을 토대로 무게를 만들 수 있다면 DP [i][j]는 true가 될 것이다.

 

dp 배열을 40001로 정적으로 잡고 싶지 않았는데, 구슬들의 무게의 합의 최댓값, 추의 무게의 최대값 등 신경 써줘야 할 것이 너무 많아서 

문제에서 주어진 최댓값인 40001로 잡았다.

전체 코드

package DP.`2629_양팔저울`.LJH

import java.io.BufferedReader
import java.io.InputStreamReader
import kotlin.math.abs

class `2629` {
    private val br =BufferedReader(InputStreamReader(System.`in`))
    private var n = 0
    private var m=0
    private var weight = Array(31) { 0 }
    private var bead =Array(8) { 0 }
    private  var dp = Array(31){ BooleanArray(40001) { false } }
    init{
        input()
        dp()
        solution()
    }
    fun input(){
        n = br.readLine().toInt()
        val line = br.readLine().split(" ")
        for(i in 0 until n)
        {
            weight[i] = line[i].toInt()
        }
        m=br.readLine().toInt()
        val token = br.readLine().split(" ")
        for(i in 0 until m){
            bead[i] = token[i].toInt()
        }
    }
    fun dp(){ //만들수 있는 무게를 구함.
        for(i in 1 .. n){
            val temp = weight[i-1]
            dp[i-1][0]=true
            for(j in 0 until dp[i].size){ //무게는 그대로, 절대값 빼기, 그냥 더하기
                dp[i][j]=dp[i-1][j] || dp[i-1][abs(j-temp)]
                if(j+temp< dp[i].size)
                    dp[i][j]= dp[i][j] || dp[i-1][j+temp]
            }
        }
    }
    fun solution(){
        for(i in 0 until m){
            if(dp[n][bead[i]])
                print("Y ")
            else print("N ")
        }
    }
}

fun main() {
    val solution = `2629`()
}