Swift - 백준 11050번 이항 계수1

이항 계수 문제는 DP를 사용하여 해결할 수 있습니다

 

파스칼의 삼각형

이항 계수를 사용하여 값을 구하게 된다면 아래와 같은 피라미드의 값이 나타납니다. 이를 파스칼의 삼각형이라고 하며 이 파스칼의 삼각형을 이해하게 된다면 특정 공식으로 값을 쉽게 해결할 수 있습니다.

 

DP

문제를 해결하기 위해서는 DP를 사용합니다.

DP는 문제를 해결하기 위해 이전값을 기억하였다가 이후 계산에 사용하는 프로그래밍 기법입니다.

 

• for 문에서 0부터 line[0] 까지 반복합니다.
  • line[0]은 위 그림에서 6번째 줄까지 값들을 구한다는 것을 의미합니다
• Swift 에서 arr[i][j] = 1 처럼 값을 추가하여 2차원 배열에 추가하려고 했지만 arr[i][j] = 1 형식은 Swift에서 지원하지 않기에 임시로 값을 담을 수 있는 tmp를 만들었습니다.
• i == j 와 j == 0 으로 조건문을 만든 이유는 첫번째 원소와 마지막 원소는 항상 1이 들어가기 때문입니다.
• DP 알고리즘을 사용하여 이전 줄의 값인 arr[i-1][j-1] + arr[i-1][j] 를 추가하여 문제를 해결할 수 있습니다.

var line = readLine()!.split(separator: " ").map { Int($0)! }

var arr:[[Int]] = []

for i in 0...line[0] {
    var tmp: [Int] = []
    for j in 0...i {
        if i == j || j == 0 {
            tmp.append(1)
        } else {
            tmp.append(arr[i-1][j-1] + arr[i-1][j])
        }
    }
    arr.append(tmp)
}

print(arr[line[0]][line[1]])