[Node.js] 구름톤 챌린지 2주 Day3 풀이 (통증)

문제

통증을 각각 14, 7, 1 만큼 줄여줄 진통제가 각각 존재한다.

통증이 주어졌을 때, 모든 통증을 줄여줄 수 있는 최소한의 진통제 사용량을 찾아서 리턴하라

 

코드

const readline = require('readline');
let rl = readline.createInterface({
	input: process.stdin,
	output: process.stdout,
});

let pain = 0;


rl.on('line', (line) => {
	pain = parseInt(line)
}).on('close', () => {
	let answer = 0
	
	for (let i of [14, 7, 1]) {
		answer += Math.floor(pain / i)
		pain = pain % i
	}
	console.log(answer)
})

 

그리디 알고리즘

문제를 해결할 때 현재의 상황에서 가장 최선의 방법을 찾아 문제를 해결하는 알고리즘이다.

현재 상황에서 가장 최선의 방법을 찾아 가므로, 전체적인 관점에서는 최선의 방법이 아닐 수 있는 알고리즘이다.

따라서 사용할 때와 사용하지 못할 때를 잘 구분하여 사용해야 한다.

 

그리디 알고리즘은 사용할 조건이 숫자이고, 조건들이 배수관계를 띄고 있을 때 사용할 수 있다.

위의 문제는 각각 진통제의 진통을 줄여주는 양이 14, 7, 1로 배수관계를 띄고 있어 그리디 알고리즘을 사용할 수 있었다.