백준 1182번 부분수열의 합 Kotlin 구현해보기

---

```

백준 1182번 부분수열의 합 Kotlin 구현해 보기

```

Kimc Kotlin Study

이번 글을 통해 배워갈 내용

1. 백준 1182번 부분수열의 합 Kotlin 풀이

---

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

1182번: 부분수열의 합

백준 1182번 부분수열의 합은

 

난이도 실버 등급의 문제로서

 

N개의 정수로 이루어진 수열이 있을 때,

크기가 양수인 부분수열 중에서

그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 구하면 됩니다

 

---

30분 정도 위에 링크를 방문하셔서 풀어보시고

안 풀리시는 경우에만 아래 해답을 봐주시면 감사하겠습니다.

---

countSubsequencesWithSum 함수에서

rec을 호출하고

rec에서 조건에 따라서

전체 숫자 사이즈를 순차적으로 재귀적으로 확인하는 방법으로 풀었습니다

 

fun main(args: Array<String>) {
    val inputDto = getInput()
    print(solution(inputDto))
}

data class InputDto(
    val expectedSum: Int,
    val nums: List<Int>
) {
    var cnt = 0

    fun countSubsequencesWithSum(): Int {
        this.cnt = 0
        rec(0, 0)
        if (isEmptySet()) this.cnt--
        return this.cnt
    }

    private fun isEmptySet() = expectedSum == 0

    private fun rec(size: Int, sum: Int) {
        if (size == nums.size) {
            if (sum == expectedSum) {
                cnt++
            }
            return
        }
        rec(size + 1, sum)
        rec(size + 1, sum + nums[size])
    }
}

fun getInput(): InputDto {
    val expectedSum = readln().split(" ").map { m -> m.toInt() }[1]
    val nums = readln().split(" ").map { m -> m.toInt() }
    return InputDto(expectedSum, nums)
}


fun solution(dto: InputDto): String {
    return "${dto.countSubsequencesWithSum()}"
}


// https://codemasterkimc.tistory.com/

 

테스트

import org.junit.jupiter.api.Assertions.assertEquals
import org.junit.jupiter.api.Test

internal class MainKtTest {

    @Test
    fun test() {
        assertEquals(
            "1",
            solution(
                InputDto(0, listOf(-7, -3, -2, 5, 8))
            )
        )
    }
}

 

 

읽어주셔서 감사합니다

 

무엇인가 얻어가셨기를 바라며

 

오늘도 즐거운 코딩 하시길 바랍니다 ~ :)

 

---