백준 5557 1학년

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

분류: DP

---

접근방식

만들 수 있는 가능한 연산의 경우의 수를 구하는 문제였습니다!

중간 중에 나올 수 있는 수는 0 ~ 20 밖에 없기 때문에
0~20까지 배열을 만들어두고 개수를 카운트 해주는 방식으로 해결했습니다.

이전 연산의 개수에 계산한 결과가 그대로 다음 연산으로 넘어가는데, 이때 이전 결과는 남아있으면 안되기 때문에 배열을 2개 두고 돌려가며 사용했습니다.

말이 조금 어려운데.. 

가령 어떻게 어떻게 해서 중간에 연산 결과가 8이 된 경우가 3개 있다고 생각하고 다음의 숫자는 3이라고 생각해보겠습니다.

그러면 +, - 연산을 사용해 8과 3으로 만들 수 있는 결과는 

8 + 3 = 11
8 - 3 = 5

이렇게 두 가지가 되고 각각의 수는 연산 전 8의 개수였던 3개가 각각 11과 5에 더해지게 됩니다.

대신 8의 3개는 없다고 생각을 해줘야하죠! 

근데 연산 결과가 5였던 경우가 있었다면 3을 더해서 새로운 8을 만들어 줄 수 있겠죠
반대로 11이 있었다면 3을 빼서 또 새로운 8을 만들 수 있구요.

그래서 이전 연산의 결과와 새로 만들어진 결과를 구분해주기 위해서 배열을 두 개 만들었습니다. 
잘 빼고 더하면 하나로 할 수도 있겠지만 좀 귀찮아 질 것 같아서요!

nextCountTable = initCountTable
countTable.enumerated().forEach { (number, count) in
    guard count != 0 else { return }
    let addition = number + numbers[idx]
    let subtraction = number - numbers[idx]
    
    if addition >= 0, addition <= 20 {
        nextCountTable[addition] += count
    }
    if subtraction >= 0, subtraction <= 20 {
        nextCountTable[subtraction] += count
    }
}
countTable = nextCountTable

이런 식으로 계산하면서 인덱스를 늘려가며 재귀적으로 해결했습니다.

 

해결방법

var n = Int(readLine()!)!
var numbers = readLine()!.split(separator: " ").map { Int(String($0))! }
var initCountTable = [Int](repeating: 0, count: 21)
var countTable = initCountTable
var nextCountTable = initCountTable

func play(_ idx: Int) {
    guard idx < numbers.count-1 else {
        print(countTable[numbers[numbers.count-1]])
        return
    }
    
    nextCountTable = initCountTable
    countTable.enumerated().forEach { (number, count) in
        guard count != 0 else { return }
        let addition = number + numbers[idx]
        let subtraction = number - numbers[idx]
        
        if addition >= 0, addition <= 20 {
            nextCountTable[addition] += count
        }
        if subtraction >= 0, subtraction <= 20 {
            nextCountTable[subtraction] += count
        }
    }
    countTable = nextCountTable
    play(idx+1)
}

countTable[numbers[0]] = 1
play(1)

배운점

디피는 왜케 어렵쥐....