Node.js) 백준 17626번: Four Squares

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

17626번: Four Squares

const input = +require('fs').readFileSync('./dev/stdin').toString().trim();
let answer = Infinity;
const sqrtArr = [];

let num = 1;
while (num * num <= input) {
	sqrtArr.push(num * num);
	num++;
}
class Node {
	constructor(item) {
		this.item = item;
		this.next = null;
	}
}

class Queue {
	constructor() {
		this.head = null;
		this.tail = null;
		this.length = 0;
	}

	push(item) {
		const node = new Node(item);
		if (this.head == null) {
			this.head = node;
		} else {
			this.tail.next = node;
		}

		this.tail = node;
		this.length += 1;
	}

	pop() {
		const popItem = this.head;
		this.head = this.head.next;
		this.length -= 1;
		return popItem.item;
	}
}

const q = new Queue();
q.push([input, 0])
let dp = Array(50000).fill(Infinity);
while (q.length > 0) {
	const [value, cnt] = q.pop();
	if (value == 0 && cnt < answer) {
		answer = cnt;
	} else {
		for (let i = sqrtArr.length - 1; i >= 0; i--) {
			const sqrt = sqrtArr[i];
			const nextValue = value - sqrt;
			if (nextValue >= 0 && cnt + 1 <= answer && dp[nextValue] > cnt + 1) {
				dp[nextValue] = cnt + 1;
				q.push([nextValue, cnt + 1]);
			}
		}
	}
}
console.log(answer);