백준 15652번 N과 M (4)

백준 15652번 N과 M (4) 문제이다.

역시 N과 M 문제이다. 단계별로 풀어보기 백트래킹 항목에 있는 마지막 N과 M 문제이다.

(다른 N과 M 문제들은 더 있다...)

이번에는 비 내림차순이라고 한다. 

다른말로 하면 오름차순에 중복까지 가능하다고 생각하면 된다.

역시 백트래킹 문제이므로 비슷하게 풀어준다. 

N과 M (2) 문제와 비교하면 편할 것 같다.

(2) 문제에서는 숫자 하나를 사용하면 그 숫자까지의 check 배열을 증가 시켰지만,

이번에는 그 숫자가 중복이 가능하므로 그 숫자 하나 아래 값 까지만 check 배열의 값을 증가시킨다.

이번 문제는 ruby 언어를 사용하였다. 

def func(cnt)
    if cnt == $m
        for i in 0...$m
            print $arr1[$arr2[i]]
            print ' '
        end
        puts
    else
        for i in 0...$n
            if $check[i] == 0
                for j in 0...i
                    $check[j] += 1
                end
                $arr2[cnt] = i
                func(cnt+1)
                for j in 0...i
                    $check[j] -= 1
                end
            end
        end
    end
end



$n, $m = gets().chomp().split()
$n = $n.to_i
$m = $m.to_i
$arr1 = [1,2,3,4,5,6,7,8]
$arr2 = [0,0,0,0,0,0,0,0]
$check = [0,0,0,0,0,0,0,0]
func(0)

오름차순 처리에 중복만 허용해주면 가능한 문제였다.

성공!