문제
집에서 시간을 보내던 오영식은 박성원의 부름을 받고 급히 달려왔다. 박성원이 캠프 때 쓸 N개의 랜선을 만들어야 하는데 너무 바빠서 영식이에게 도움을 청했다.
이미 오영식은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이다. 박성원은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다. 예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면 20cm는 버려야 한다. (이미 자른 랜선은 붙일 수 없다.)
편의를 위해 랜선을 자르거나 만들 때 손실되는 길이는 없다고 가정하며, 기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다고 가정하자. 그리고 자를 때는 항상 센티미터 단위로 정수길이만큼 자른다고 가정하자. N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다. 이때 만들 수 있는 최대 랜선의 길이를 구하는 프로그램을 작성하시오.
입력
첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 후 K줄에 걸쳐 이미 가지고 있는 각 랜선의 길이가 센티미터 단위의 정수로 입력된다. 랜선의 길이는 231-1보다 작거나 같은 자연수이다.
출력
첫째 줄에 N개를 만들 수 있는 랜선의 최대 길이를 센티미터 단위의 정수로 출력한다.
https://www.acmicpc.net/problem/1654
주어진 숫자가 크기에 이분탐색을 사용하여 풀어야 합니다.
- 입력부분과 나누어 떨어지는 숫자를 저장하는 객체를 만든다.
let input = `4 11
802
743
457
539`.toString().split('\n')
const [k, n] = input.shift().split(' ').map(e => Number(e))
const cables = input.map(e => Number(e)).sort()
let cases = {}
// 각각 케이블에서
// N 번 만큼 각 케이블들을 나눠보고 떨어지는 경우 케이블스에 저장한다
for (let i = 2; i < n; i++)
{
for (let c = 0; c < k; c++)
{
if (cables[c] % i < 3) //나누어 떨어진다!(소숫점 첫째까지 허용)
{
if(!cases[cables[c]]) cases[cables[c]] = []
const doubleCheck = cases[cables[c]].includes(i)
if(!doubleCheck)
{
cases[cables[c]].push(i)
}
}
}
}나눈 횟수가 총 11이 되도록 경우의 수를 백트랙킹으로 구할 것이다. 각 케이블들의 가능한 나눔의 수를 배열에 추가해보며 11이 되었을 때 반복을 중단한다
- 메모이제이션을 위한 방문 배열을 만든다.
let visit =
Array.from(Object.values(cases)).map( e => e.map( a => -1))- 백트레킹 함수
const back = (arr,i,now) =>
{
if(arr.length > 0)
{
let sums = arr.reduce((a,b) => a + b)
if( sums === 11 && arr.length ===k)
{
let cablesLength = [] // 조합으로 나누었을 때 각 케이블의 길이
let sizeRange = [] // 케이블 길이의 첫번째 자리수 저장
let prev = 0 // 자리수가 같은지 비교하기 위한 변수
let isInSameRange = false // 자리수가 다르면 반복을 멈추게 함
for(let i = 0; i < arr.length; i++)
{
// 첫번째 자리수를 저장한다
let a = Math.floor(cables[i]/arr[i]).toString()[0]
sizeRange.push(a)
// 조합으로 나누었을 때 각자 케이블의 최소 길이 저장
cablesLength.push(Math.floor( cables[i]/arr[i]))
}
// 나누었을 때 요소들의 조합들이 같은 사이즈 내에 있는지 확인
for(let j = 0; j < sizeRange.length; j ++)
{
if(prev === 0) prev = sizeRange[j]
if(prev !== sizeRange[j])
{
// 자리수가 바로 다르면 멈춘다
isInSameRange = false
break
}
if(prev === sizeRange[j] && sizeRange[j] === sizeRange[0])
{
prev = sizeRange[j], isInSameRange =true
}
// 반복 마지막 부분에서 모든 자리수가 같다면,
// 나누었을 때 비슷한 사이즈의 조합들을 찾고 가장 작은 요소를 찾는다.
if(j === sizeRange.length-1 && isInSameRange)
//802cm 랜선에서 4개, 743cm 랜선에서 3개, 457cm 랜선에서 2개,
//539cm 랜선에서 2개를 잘라내 모두 11개를 만들 수 있다.
console.log('정답',arr)
console.log(Math.min.apply(null,cablesLength))
}
}
}
}
// 케이블을 자를 수 있는 경우의 수를 이용하여 백트래킹을 시작한다
for(const [key,val] of Object.entries(cases))
{
// 현재 케이블과 같다면
if(now == key)
{
// 모든 가능한 경우의 수를 시험해본다.
for(let o = 0; o < val.length -1; o ++)
{
// 사용하지 않은 경우의 수를 선택한다
if(visit[i][o] < 0 )
{
// 방문배열에 사용한 경우의 수를 저장해준다
visit[i][o] === val[o]
arr.push(val[o])
// 다음 케이블로 이동한다.
back(arr,i+1,cables[i+1])
arr.pop()
visit[i][o] === -1
}
}
}
}
}
back([],0,cables[0])