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

문제

• 게임에 통증이라는 시스템이 있음.
• 게임 안에는 통증 수치를 감소시켜 주는 아이템인 A와 B가 있음.
• 각 아이템은 사용시 각각 A, B만큼 통증을 감소시켜 줌. 각 아이템은 원하는대로 획득 가능
• N의 통증 수치가 주어졌을 때, 통증 수치를 0으로 만들 수 있는 아이템 A와 B의 최소 사용 갯수를 구해야 함

 

코드

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

let input = [];

rl.on('line', (line) => {
	input.push(line.trim())
}).on('close', () => {
	const N = parseInt(input[0])
	const [A, B] = input[1].split(" ").map(Number)
	
	// 최소값을 찾는 것이므로 Infinity로 초기화
	const DP = Array(N + 1).fill(Infinity)
	
	// DP에서는 기본값 설정이 중요
	// 배열 index를 통증으로 정의하고 배열 값을 통증에 사용할 진통제 갯수로 정의
	// 통증이 0일때는 써야할 진통제가 없으므로 DP[0] = 0
	DP[0] = 0
	
	// DP[0]은 값이 할당되어 있으므로 1부터 시작
	// [통증 - 진통제]가 0보다 크거나 같을 경우, 해당 진통제는 사용 가능함.
	// A가 2이고 B가 7일때 진통9에서 7만큼 빠진거라면 DP[9 - 7] + 1이라는 생각을 해볼 수 있음
	// DP[9 - 7]의 값은 동적 프로그래밍을 통해 이미 채워져 있을 것임
	for (let i = 1; i < DP.length; i++) {
		if (i - A >= 0) DP[i] = Math.min(DP[i], DP[i - A] + 1)
		if (i - B >= 0) DP[i] = Math.min(DP[i], DP[i - B] + 1)
	}
	
	const target = DP.at(-1)
	console.log(target !== Infinity ? target : -1)
})

 

DP

DP는 값을 메모이제이션해서 문제를 해결하는 알고리즘의 한 종류인데, 여기에서는 진통제 최소 사용 갯수를 기록하는 용도로 사용되었다. 통증 N이 주어졌을 때 통증을 0으로 만드는 아이템의 최소 사용 갯수를 직관적으로 구하는 것은 컴퓨터의 입장에서는 상당히 어려운 작업이기 때문에, 1부터 N까지 아이템의 최소 사용갯수를 모두 기록하면서 문제를 해결하였다.

 

DP를 사용하려면 문제의 정의와 규칙을 미리 알아야 한다.
즉, DP 자체가 어렵다기 보다는 문제를 이해하고, 조건을 정의하는게 어렵다.