반응형 다이나믹 프로그래밍1 [Algorithm/BOJ] 5557 - 1학년 (DP) Swift 문제풀이: 완전탐색으로 접근하면 시간초과가 난다. 그러면 DP로 풀어야 하는데 DP는 항상 접근 방법을 찾기가 어려웠다. 이전의 숫자 정보와 덧셈과 뺄셈을 진행할 index를 필요로 해서 2차원 배열로 사용해야 한다. 위 그림과 같이 처음에 dp[0][8]을 시작으로 다음 수인 3을 뺀 결과와 더한 결과가 0보다 크거나 같고 20보다 작거나 같으면 dp에 값을 저장한다. 이후는 같은 과정으로 진행하고 마지막 수에 해당하는 경우의 수를 출력한다. 코드: let n = Int(readLine()!)! var nums = readLine()!.split(separator: " ").map { Int(String($0))! } var dp = [[Int]](repeating: [Int](repeating: 0,.. 2021. 4. 29. 이전 1 다음 반응형