[알고리즘] Swift -백준 #11051(이항 계수 2) -DP

문제링크

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

11051번: 이항 계수 2

 

문제

자연수 N과 정수 K가 주어졌을 때 이항 계수 {N K}를 10,007로 나눈 나머지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ K ≤ N)

출력

{N K}를 10,007로 나눈 나머지를 출력한다.

예제 입력 1 

5 2

예제 출력 1 

10

 

 

 

 

분석

이항계수 표 (파스칼의 삼각형)

nCk 를 구하는 문제

nCk = n-1Ck-1 + n-1Ck

 

풀이 과정

배열의 처음과 끝의 값은 무조건 1으로 설정

var map = Array(repeating: Array(repeating: -1, count: n+1), count: n+1)

map[0][0] = 1
for i in 1..<n+1 {
    map[i][0] = 1
    map[i][i] = 1
}

 

반복문을 사용하여 이항계수를 계산해준다.

for i in 1..<n+1 {
    for j in 0..<n+1 {
        if map[i][j] < 0 {
            map[i][j] = map[i-1][j-1] + map[i-1][j]
        }
    }
}

그리고 10007로 나눈 나머지를 출력했다.

print(map[n][k] % 10007)

 

 

n의 최대값인 1000을 넣었더니 런타임 에러나 났다.

오버플로우가 발생했기에 나머지 값을 먼저 배열에 넣는 방식으로 변경하였다.

이 부분을 고치는데 조금 오래거렸다..

for i in 1..<n+1 {
    for j in 0..<n+1 {
        if map[i][j] < 0 {
            map[i][j] = (map[i-1][j-1] + map[i-1][j]) % 10007
        }
    }
}

print(map[n][k])

나머지끼리의 연산은 나중에 나누어주는 것과 같다!

 

 

풀이

let input = readLine()!.split(separator: " ").map{ Int($0)!}
let (n, k) = (input[0], input[1])

var map = Array(repeating: Array(repeating: -1, count: n+1), count: n+1)

map[0][0] = 1
for i in 1..<n+1 {
    map[i][0] = 1
    map[i][i] = 1
}

for i in 1..<n+1 {
    for j in 0..<n+1 {
        if map[i][j] < 0 {
            map[i][j] = (map[i-1][j-1] + map[i-1][j]) % 10007
        }
    }
}

print(map[n][k])

 

결과

 

 

 

---

📂  정리

런타임에러가 났을 떄 해결을 잘 해야한다.

여기서 한번 헤매기 시작하면 머리가 아파서 포기할지도 ㅎㅎ