[Algorithm]BOJ_2407_조합_Go

문제 링크

조합

해결 방법

1. 조합은 nCm = n-1Cm-1 + n-1Cm 식이 성립한다. (코드에서 변수 combi를 통해 combi[n][m]와 같은 방법으로 표현)
2. 조합은 n=m인 경우와 m=0인 경우 값은 1이다.
3. 1.점화식을 활용하여 dp를 사용하여 해결한다.
4. 조합의 경우 값이 몹시 크기 때문에 string Type의 덧셈 함수를 제작하여 사용한다.

package main

import (
    "fmt"
    "strconv"
)

//큰수의 합 문제

const (
    max = 101
)

var answer string
var N, M int
var combi [max][max]string

// string type의 값을 int type값으로 캐스팅
func getInt(val byte) int {
    value, _ := strconv.Atoi(string(val))
    return value
}

// 올림이 존재하는지 확인
func isOlim(val int) bool {
    if val >= 10 {
        return true
    }
    return false
}

// 큰수를 더하는 함수
func calc(n, m string) string {
    var answer string
    if len(n) < len(m) {
        n, m = m, n
    }
    long := len(n)
    short := len(m)
    var tmp int
    olim := false

    for i := 1; i <= len(n); i++ {
        var longVal int
        var shortVal int
        if short-i < 0 {
            shortVal = 0
        } else {
            shortVal = getInt(m[short-i])
        }
        longVal = getInt(n[long-i])
        tmp = shortVal + longVal
        if olim {
            tmp++
        }
        olim = isOlim(tmp)
        answer = strconv.Itoa(tmp%10) + answer
    }
    if olim {
        answer = "1" + answer
    }
    return answer
}

// nCm = n-1Cm-1 + n-1Cm 점화식을 재귀 형식으로 풀이
func combination(n, m int) string {
    if n == m || m == 0 {
        combi[n][m] = "1"
        return "1"
    }
    if combi[n-1][m-1] == "" {
        combination(n-1, m-1)
    }
    if combi[n-1][m] == "" {
        combination(n-1, m)
    }
    combi[n][m] = calc(combi[n-1][m-1], combi[n-1][m])
    return combi[n][m]
}

func main() {
    fmt.Scan(&N, &M)
    combination(N, M)
    fmt.Println(combi[N][M])
}