백준 14889번 스타트와 링크

백준 14889번 스타트와 링크 문제이다.

이번 문제는 설명이 매우 길다. 사람을 두 그룹으로 나누어 묶고 시너지 표를 보고 각 그룹의 시너지의 차이를 구하면 된다.

이해가 잘 안된다면 입출력 예시를 본다.

이번 문제도 백트래킹 문제이기 때문에 한 그룹에 사람을 한명씩 넣어가도록 한다.

한 그룹에 사람이 반절 차게 되면 다른 한 그룹도 정해지게 된다.

그룹이 정해지는 순간 시너지 표에서 각 그룹의 시너지 합을 구해 차를 비교해준다.

차가 최솟값이 되어야 하기 때문에 최솟값으로 구해진 값과 비교하여 갱신해준다. 

여기서 생각해줘야 할 점은 solve 함수에 들어간 k값이다. k 값을 넣음으로써 그룹에 한 사람이 들어갔다면 

다시 처음사람부터 확인하는 것이 아니라 k번째 다음 사람부터 확인이 가능하다.

def solve(k, cnt)
    if cnt == ($n/2)
        result = calc()
        if $gap > result
            $gap = result
        end
    else
        for i in k...$n
            if $human[i] == 1
                $human[i] -=1
                solve(i, cnt+1)
                $human[i] +=1
            end
        end
    end
end
def calc()
    check = 0
    check2 = 0
    sum1 = 0
    sum2 = 0
    pick = Array.new($n/2){0}
    pick2 = Array.new($n/2){0}
    for i in 0...$n
        if $human[i] == 0
            pick[check] = i
            check += 1
        else
            pick2[check2] = i
            check2 += 1
        end
    end
    for i in 0...$n/2
        for j in i+1...$n/2
            sum1 = sum1 + $arr[pick[i]][pick[j]] + $arr[pick[j]][pick[i]]
            sum2 = sum2 + $arr[pick2[i]][pick2[j]] + $arr[pick2[j]][pick2[i]]
        end
    end
    return ((sum1 - sum2).abs)
end

            

$n = gets().chomp().to_i
$arr = Array.new($n) {Array.new($n){0}}
$human = Array.new($n){1}

$gap = 100000
for i in 0...$n
    $arr[i] = gets.chomp().split()
    for j in 0...$n
        $arr[i][j] = $arr[i][j].to_i
    end
end
solve(0, 0)

puts($gap)

언어는 ruby를 사용하였다. 

성공!