백준 DP 알고리즘, 2688 줄어들지않아 swift 문제풀이

 

 

 

오늘은 swift로 백준문제, 2688번 줄어들지않아 를 풀어보겠습니다.

해당 문제는 N자리의 줄어들지 않는 수의 모든 경우의 수를 구하는 문제입니다. 바로 문제를 살펴보겠습니다. 

 

 

 

 

 

---

swift 백준문제, 2688 줄어들지 않아 문제 설명

ㄴ

줄어들지 않아 문제는 골드5로, 중급 수준의 알고리즘 문제입니다. 

 

 

 

시간제한은 1초로, 1억 번의 연산 미만의 복잡도의 알고리즘을 강구해야 합니다. 

 

 

 

 

문의 설명은 위와 같습니다. N자리의 줄어들지 않는 수 경우의 수를 출력하면 됩니다.

예를들면, 줄어들지 않는 수는 0011, 0112, 0001, 1234 등이 있습니다.

이번 문제는 DP(Dynamic Programming)의 방법으로 풀 수 있습니다. 더욱이, 해당 문제는 T를 입력 받아 여러번의 쿼리 결과값을 얻어야 하는 만큼, DP로 미리 모든 N자리 경우의 수를 구하고 나면 더욱 효율적인 속도로 문제를 해결 할 수 있습니다. 

 

 

---

swift 백준문제, 2688 줄어들지 않아 입출력 결과

 

입출력 결과 예시입니다. 먼저 입력 된 3은 3번의 쿼리 입력을 받는 다는 것입니다. 이후 2, 3, 4를 입력 받은 것은 2, 3, 4자리의 내려가지않는 수 경우의 수를 출력하는 것이 됩니다. 

 

바로 swift 코드로 DP(Dynamic Programming)방식을 사용해 구현해보도록 하겠습니다. 

 

 

---

2688 줄어들지 않아 swift 코드 구현하기

먼저 Int 타입 값을 입력 받는 클로져를 선언했습니다. 해당 클로져는 이후 변경될 필요가 없는 클로져로 상수로 선언했습니다. 중복된 입력 코드를 줄여줘서 보다 직관적으로 코드를 짤 수 있어서 이렇게 사용하게 되었습니다.

 

len은 1 ~ 64자리까지의 입력값에 대응하기 위한 최대 길이, 65를 선ㄴ언한 상수 len입니다. 

 

 

 

 

DP값을 기록해둘 2차원 배열을 선언합니다. 1 ~ len-1(64) 까지의 N 자리수에 대해서 끝에 0 ~ 9의 숫자를 두었을때의 모든 경우의 수를 누적해서 기록하게 됩니다.

 

예를 들면, DP[idx][jdx] -> idx자리의 수의 끝자리가 jdx 숫자가 들어가는 모든 경우의 수가 됩니다.

 

 

 

 

15행) 각각의 쿼리 입력값 결과를 출력하기 전에, DP방식으로 모든 경우의 수를 기록하는 코드입니다. 1 ~ 64(DP.count-1) 자리일 경우의 모든 경우의 수를 기록합니다. 

 

18행) idx == 1일때의 분기를 두는것은 1자리 일 경우에는 어떤 숫자를 두어도 그 모든 경우의 수는 각각 1이기 때문입니다.

21행) idx > 1일 경우에는 점화식을 적용하게 됩니다. 점화식은 DP[idx][jdx] = DP[idx-1][jdx] + sum(idx-1 자리에서 0 ... jdx-1 의 숫자를 두는 모든 경우의 수) 가 됩니다. 

예를들면, 한자리수에서 끝에 '6'을 두는 경우의 수는 '6' 단 하나입니다. 

 

이렇게 DP를 기록하면 N 자리수의 모든 경우의 수는 DP[N][...] 의 합이 됩니다.

DP[N][...]는 DP[N][0] + DP[N][1] + DP[N][2] + ... DP[N][9] 입니다.

 

 

 

이제 DP 배열에 모든 경우의 수를 기록했습니다. T를 입력받고, T번 입력받은 쿼리의 값을 출력합니다. 

 

 

DP[N].reduce(0, +)

34행) 0을 초기값으로 해서 DP[N][...]의 모든 합을 구하게 됩니다. 이 값이 N자리의 내려가지않는 수의 경우의 수가 됩니다. 

reduce는 해당 배열의 값을 특정 조건에 따라 하나의 결과값으로 합쳐주는 고차함수로, 이번 문제에서는 모든 배열 값의 합을 구하는데 사용되었습니다

 

 

---

swift 코드 제출 결과