티스토리 뷰

자료구조 알고리즘/백준

Node.js)백준 1208번: 부분수열의 합 2

LHOIKTN 2022. 1. 8. 01:39

https://www.acmicpc.net/problem/1208

 

1208번: 부분수열의 합 2

첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.

www.acmicpc.net

 

 

 

참고,, 먼저 풀어보면 좋은 문제

const input = require('fs').readFileSync('./dev/stdin').toString().trim().split('\n').map(v=>v.trim())
const [N,S] = input[0].split(' ').map(Number)
const A = input[1].split(' ').map(Number)
let memo = new Map();
let answer = 0;
const L = Math.floor(N/2);
const B = A.splice(L)

for(let bit =1; bit<(1<<A.length); bit++){
  const sum = A.filter((_,index)=>bit&(1<<index)).reduce((r,v)=>{return r+v},0)
  if(sum==S) answer++;
  memo.set(sum,(memo.get(sum) ?? 0)+1)
}

for(let bit =1; bit<(1<<B.length); bit++){
  const sum = B.filter((_,index)=>bit&(1<<index)).reduce((r,v)=>{return r+v},0)
  if(sum==S) answer++;
  answer+= memo.get(S-sum) ?? 0;
}

console.log(answer)
728x90

'자료구조 알고리즘 > 백준' 카테고리의 다른 글

Node.js)백준 16968번: 차량 번호판 1  (0) 2022.01.08
Node.js)백준 2003번: 수들의 합 2  (0) 2022.01.08
Node.js)백준 2143번: 두 배열의 합  (0) 2022.01.08
Node.js)백준 15666번: N과 M (12)  (0) 2022.01.07
Node.js) 백준 15665번: N과 M (11)  (0) 2022.01.07
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
TAG more
«   2025/02   »
일 월 화 수 목 금 토
1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25 26 27 28
글 보관함