[Nodejs] 구름_사은품 교환하기

문제

https://level.goorm.io/exam/47878/%EC%82%AC%EC%9D%80%ED%92%88-%EA%B5%90%ED%99%98%ED%95%98%EA%B8%B0/quiz/1

구름LEVEL

 

 

풀이

문제의 입력 값의 조건을 살펴보면 64비트 부호형 정수형 범위내에 존재하는 0이상의 정수라고 말한다.

이는 BigInt를 사용한다는 것이며, 일반적으로 Number와 Math 모듈을 같이 사용하면 안된다.

 

나는 이 문제를 풀때 실수한 것이 BigInt를 사용하지만, 반복문을 이용해 문제를 풀었다.

O(2n^2) 정도의 시간복잡도가 나왔으며 일반적인 Number 형식이였으면 풀렸겠지만, BigInt이다 보니 시간초과 에러가 발생한 것같다.

 

수학적인 풀이로 접근했다.

우선 일반 쿠폰이 최소 5개가 있어야 교환이 가능하기에 5개씩 몇번 낼 수 있는지 측정하고, 일반과 스페셜 쿠폰 두가지 쿠폰을 합쳐 12장인 경우 몇번을 낼 수 있는지 측정한다.

 

이때 일반 쿠폰 5개가 있는 경우와 두 쿠폰 12장이 있는 경우를 비교해 더 적은 쪽의 경우를 선택한다.

 

 

코드

// Run by Node.js
const readline = require("readline");
const rl = readline.createInterface({
	input: process.stdin,
	output: process.stdout
});
let input = [];
let TC = null;

const sol = ([normal, special]) => {
	const k1 = normal / 5n;
	const k2 = (normal + special) / 12n;
	let cnt = k1 < k2 ? k1 : k2;
	
	console.log(String(cnt));
}

rl.on("line", function(line) {
	if(TC === null){
		TC = +line;
	}
	else{
		sol(line.split(' ').map(e => BigInt(e)));
		TC--;
	}
	if(!TC){
		rl.close();
	}
}).on("close", function() {
	process.exit()
});