백준 5557) 1학년

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

5557번: 1학년

 

문제

상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀고 있다. 예를 들어, "8 3 2 4 8 7 2 4 0 8 8"에서 등식 "8+3-2-4+8-7-2-4-0+8=8"을 만들 수 있다.

상근이는 올바른 등식을 만들려고 한다. 상근이는 아직 학교에서 음수를 배우지 않았고, 20을 넘는 수는 모른다. 따라서, 왼쪽부터 계산할 때, 중간에 나오는 수가 모두 0 이상 20 이하이어야 한다. 예를 들어, "8+3+2-4-8-7+2+4+0+8=8"은 올바른 등식이지만, 8+3+2-4-8-7이 음수이기 때문에, 상근이가 만들 수 없는 등식이다.

숫자가 주어졌을 때, 상근이가 만들 수 있는 올바른 등식의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 숫자의 개수 N이 주어진다. (3 ≤ N ≤ 100) 둘째 줄에는 0 이상 9 이하의 정수 N개가 공백으로 구분해 주어진다.

출력

첫째 줄에 상근이가 만들 수 있는 올바른 등식의 개수를 출력한다. 이 값은 2^63-1 이하이다.

 

 

---

 

 

접근 방법

 

마지막 두 숫자에 등호 '=' 을 넣고 나머지 숫자 사이에는 '+' 또는 '-'를 넣어야 한다.

그렇다면 숫자의 개수 N이 주어질 때,

N-2까지는 '+' 또는 '-'로 어떻게든 구하고, 마지막으로 N-1 의 값과 비교해서 같은지를 찾아야 한다.

 

 

 

그렇다면 i번 째(0 <= i <= N-2)가 됐을 때 0 ~ i-1 까지는 어떤 연산을 거쳤는지 알 수 없다.

 

백준 강의를 통해 배우면서 "알 수 없는 정보"가 매우 중요하다고 강조했다.

이것이 바로 다이나믹 프로그래밍 기법을 사용하는 이유이기 때문이다.

 

D[i][j] = i 번째 수일 때 연산의 결과가 j가 되는 경우의 수라면

'+', '-' 연산 두 가지를 수행할 수 있기 때문에

 

(0~i-1까지 더하고 뺀 수) + A[i] = j

(0~i-1까지 더하고 뺀 수) - A[i] = j

 

와 같이 표현할 수 있게 된다.

 

 

이를 일반화하게 된다면

 

∑A[i-1] = j - A[i]

∑A[i-1] = j + A[i]

 

결국 D[i][j] = D[i-1][j-A[i]] + D[i-1][j+A[i]] 의 점화식을 세울 수 있다.

단, 문제 조건에서 중간에 나오는 수가 0 이상 20 이하라고 했기 때문에 범위 설정을 잘해줘야 한다.

범위 설정 조건은 아래의 소스 코드에 작성했다.

 

 

 

Top-Down 소스코드

 

Top-Down 에서는 메모제이션 기법을 이용하기 위해 -1로 전체 초기화했다.

재귀 용법을 이용하기 위해 i는 0부터 시작하되, i==N-2, 즉 i가 증가되므로 인자의 x에 +1을 넣었다.

 

lateinit var dp : Array<LongArray>
lateinit var a : List<Int>
var n = 0
fun main() = with(System.`in`.bufferedReader()) {
    n = readLine().toInt()
    a = readLine().split(" ").map { it.toInt() }
    dp = Array(n+1) { LongArray(21) { -1L} }

    println(go(0,a[0]))
}

private fun go(x : Int, y : Int) : Long {
	//예외 case
    if(y !in 0..20) return 0
    //정답 조건
    if(x == n-2) {
        return if(a.last() == y) 1
        else 0
    }
    //memozation 기법 이용
    if(dp[x][y] != -1L) return dp[x][y]

	//모든 경우의 수를 따져야 하므로 다 더한 후에 return
    //x의 인자로 x+1, y의 인자로는 y +- a[x+1] (다음 것을 더해줌)
    var ans = 0L
    ans += go(x+1, y + a[x+1]) + go(x+1, y - a[x+1])
    dp[x][y] = ans
    return ans
}

 

 

 

Bottom-Up 소스코드

 

fun main() = with(System.`in`.bufferedReader()) {
    val n = readLine().toInt()
    val a = readLine().split(" ").map { it.toInt() }
    val dp = Array(n-1) { LongArray(21)}

	//0번 째는 0번 째 수와 같으므로 경우의 수가 1 
    dp[0][a[0]] = 1

	//n-2까지 +,- 연산 수행
    for(i in 1 until n-1) {
        for(j in 0..20) {
            if(j - a[i] >= 0)
                dp[i][j] += dp[i-1][j-a[i]]
            if(j + a[i] <= 20)
                dp[i][j] += dp[i-1][j+a[i]]
        }
    }
    
    //n-2번째가 됐을 때 결과가 a의 마지막 값의 총 경우의 수
    println(dp[n-2][a.last()])
}

 

 

34401361. Bottom Up 결과

34401287. Top Down 결과