백준 2248 이진수찾기 JS

HG·2022년 8월 11일
0

백준

목록 보기
1/2
post-thumbnail

이 문제를 처음 접했을때 나의 생각은 간단했다.

2의 31승이면 2의 10승이 1000이니깐 대충 1억?정도면 그냥 전부다 스캔해도 O(n)으로 시간초과가 안나지 않을까 였다.

근데 보통 이런 생각은 늘 틀린다. 이런게 되면 굳이 알고리즘 문제가 아니었을거다.

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "example.txt";
const splitType = process.platform === "linux" ? '\n' : '\r\n'
let input = fs.readFileSync(filePath).toString().trim().split(splitType); /// /dev/stdin

// 5 3 19면

// 5자리중에서 3개 이하의 비트만 1이면 11100 11010 11001 10110 10101 10011 01110 01101 01011 00111 이게 아니다.

// 5C3 5C2 5C1 5C0 순으로 10 10 5 1 총 26이다. 

// 순서대로 쓰면

// 00000, 00001, 00010, 00011, 00100, 00101, 00110, 00111, 01000, 01001, 01010, 01011, 01100, 01101, 01110, 10000, 10001, 10010, 10011, 10100, 10101, 10110
let [size,key,target] = input[0].split(' ');// size 전체크기, key 1의 갯수, target 목표갯수
let count =0;
let answer;
const oneCounter = (string) =>{
    let arr = string.split('');
    return arr.reduce((prev,cur) => parseInt(prev)+parseInt(cur));
}


for(let i=0; i< Math.pow(2,size); i++){
    if(oneCounter(i.toString(2)) <= parseInt(key))  count++;
    if(count == parseInt(target)) {
        answer = i.toString(2);
    }
}

console.log(answer)

그래서 초기에 이런 코드가 생겨났다.

1의 갯수만 체크하자라는 느낌으로 접근했다 ㅎㅎ 당연히 시간초과가 났고

그리고나서 이제 좀 문제답게 접근해보고자하고 다시 풀었다.

//난 이런 문제를 풀때 늘 예제를 하나하나 써보는편이다.

//점화식도 n=1 부터 막 하나하나 써보면 뭔가 보이는 것처럼 말이다.

처음 풀이는 2진수로 다 바꾸거에서 1의 갯수가 key보다 많으면 count하지 않는 거였다.

근데 이 문제는 그냥 피보나치수열과 크게 다를게 없다.

5자리 숫자에 1을 3개 이하로 쓰는거는

첫자리에 1을 쓰고 나머지 4자리에서 1을 2개 이하로 쓰는 경우 (1) + 첫자리에 0을 쓰고 나머지 4자리에 1을 3개 이하로 쓰는 경우 (2)와 같다.

이거를 한번 더 풀어서 쓰면

(1)경우는 다시 첫자리에 1을 쓰고 나머지 3자리에 1을 한개이하 쓰는 경우(1-1) + 첫자리에 0을 쓰고 나머지 3자리에 1을 2개 이하로 쓰는 경우(1-2)로 쪼개지고

(2)경우도 마찬가지로
첫 자리에 1을 쓰고 나머지 3자리에 1을 2개 이하 쓰는 경우(2-1) + 첫자리에 0을 쓰고 나머지 3자리에 1을 3개 이하로 쓰는 경우(2-2)로 쪼개진다.

x자리중 y갯수 이하 1만 쓰는 경우를 (x,y)라고 한다면

(x,y) = (x-1,y-1)//첫자리에 1을쓴경우 + (x-1,y)//첫자리에 0을 쓴 경우

이 점화식이 그대로 진행된다.

(5,3) = (4,2) + (4,3) = 26
(4,2) = (3,1) + (3,2) = 11
(4,3) = (3,2) + (3,3) = 15
(3,1) = (2,0) + (2,1) = 4
(3,2) = (2,1) + (2,2) = 7
(3,3) = (2,2) + (2,3)-> 불가능
(2,1) = (1,0) + (1,1) = 3
(n,n)으로 같아졌을땐 그냥 2^n로간다.
(n,0)일때는 1

이 3가지 케이스가지고 문제를 푼다.

19번째를 찾기 위해서는 비교를 해야하는데

해당 과정을 Top-down형식으로 가면서 찾으면된다.

해당 프로세스를 통해 dp[x,y]로 값을 정렬해놓고, 값과 비교하면서 찾는다.

위 문제에서 19를 찾는다면

(4,3)은 앞에 0이 있고 (4,2)는 1이 맨 앞에 1이 있으므로 순서상 (4,2)의 집단의 가장 작은 수가 (4,3)의 가장 큰 수보다 크다. 19라는 수는 15보다 크므로 (4,2)의 집단으로 가면서 (1xxxx)가 됨을 알 수있다.
(4,2) 집단에서 19라는 수는 (3,1) 집단과 (3,2)사이의 중간인 22보다 작으므로 (3,2)로 가면서 (10xxx)임을 알 수있다. (2,1)집단보다 작거나 같기 때문에 (100xx)인데 (2,2)보다 크건나 같으므로 (10011)이다. 딱 중간에 있어서 좀 애매해 보이는데 예시를 19가 아닌 20으로 했다면 (2,1)보다 크거나 같으므로 (101xx)가 됐을거고 (1,0)과 (1,1)사이인 21보다 작으므로 (1010x)가 되고 남은값이 1이므로 1로 2진수 처리하면 (10101)이 된다.

이 (n,n)의 집단에 들어가면 경계를 나눌 수 없기 때문에 target값에서 중간값을 뺀 후 2진수 처리하면된다.
로 풀려고 생각하고 문제를 풀었다. 근데 이게 구현이 좀 번거로웠다.

중간에 분기처리 해주는데 헷갈리고 좀 짱났는데, 굳이 그렇게 할 필요가 없었다.
//////////////////

그냥 4C0 4C1 4C2 4C3까지 합 sum 보다 target이 크면 위의 (4,3)보다 큰거니까 1을 처리해주고 target에서 sum을 빼준 값을 target으로 변경해주고 넘겨주면된다.

그리고 3C0 3C1 3C2 3C3의 합 sum 보다 target이 작다. (3,3)보다 작은거니깐 0을 처리해주고 target을 그대로 넘겨주고 넘어간다.

2C0 2C1 2C2의 합 sum 보다 target이 같다. 같을땐 0을 처리해주고 target을 그대로 넘겨준다. 같을때 0으로 해주는 이유는 target은 순서를 말하고 1부터 시작하기 때문이다. 그때의 1은 2진수로 0으로 시작하기 때문에 같을땐 0을 처리해준거다. 이렇게 하기 싫다면 같을때 1을 하게 분기 시켜놓고 target 시작점을 1 빼고 시작해도 결과는 같다.

아무튼 이렇게 처리하면 결과는 나오고 코드는

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "example.txt";
const splitType = process.platform === "linux" ? '\n' : '\r\n'
let input = fs.readFileSync(filePath).toString().trim().split(splitType); /// /dev/stdin

// 5 3 19면

// 5자리중에서 3개 이하의 비트만 1이면 11100 11010 11001 10110 10101 10011 01110 01101 01011 00111 이게 아니다.

// 5C3 5C2 5C1 5C0 순으로 10 10 5 1 총 26이다. 
let [size,key,target] = input[0].split(' ');

let dp = Array.from(new Array(parseInt(size) +1 ), ()=> new Array(parseInt(size) +1).fill(0));
let answer = '';
dp[0][0] = 1;
for (let i =1; i<=parseInt(size); i++){
    dp[i][0] = 1;
    dp[i][i] = 1; 
}
for (let i =2; i<=parseInt(size); i++) {
    for (let j=1; j<=i; j++) {
        dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
    }
}
const findVal = ( s, k , t ) => {
    if (s === 0) return;
    if (k === 0) {
        for(let i =0; i<s; i++) {
            answer +='0';
        }
        return
    }
    let sum = 0;
    for (let i=0; i<=k; i++) {
        sum+=dp[s-1][i];
    }
    if(sum > t){
        answer +='0';
        findVal(s-1,k,t);
    }else {
        answer += '1';
        findVal(s-1,k-1,t-sum);
    }
    return


}
findVal(parseInt(size),parseInt(key),parseInt(target-1));
console.log(answer)

가 된다.

쉽지 않은 문제였다... 막 어려운 사고를 요하는게 아닌데

엄청 헷갈려서 헤맸다. 다음엔 더 잘하겠지 하는 마음으로 넘어간다..

profile
Making Body, Making Food, Making Co?de

0개의 댓글