구름톤 챌린지 12일차 일기

문제 11. 통증 (2)

let N, input, A, B;

rl.on('close', () => {
	let usedBMod = N % B;
	let usedBCnt = Math.floor(N / B);
	let usedACnt;
	
	while (usedBCnt !== -1) {
		if (usedBMod % A === 0) {
			usedACnt = Math.floor(usedBMod / A)
			return console.log(usedACnt + usedBCnt)
		} else {
			usedBCnt--;
			usedBMod += B;
		}	
	}
	return console.log(-1)
})

A 아이템이 항상 B 아이템보다 능력 수치가 낮음, B 값이 크므로

usedBMod 변수에 총 통증 수치에서 B 아이템만을 최대로 사용했을 때 남는 통증 값을 미리 저장해둔다.

usedBCnt 변수에는 그 때 최대로 사용한 갯수를 미리 저장해둔다.

 

usedBCnt 변수가 0이 될때까지 while 문을 돌면서, B 아이템을 사용하지 않을 경우까지 생각한다.

 

usedBMod 나머지 값에서 A 아이템만을 사용했을 때 나머지가 없다면,

지금까지 B 아이템 사용 갯수 + A 아이템 사용해야할 갯수를 더해서, 최소 갯수를 return 해준다.

 

하지만 A 아이템을 사용해도 나머지가 남게 된다면,

B 아이템 사용한 갯수를 하나 빼고 usedBMod에 B수치만큼 증가시켜서 나머지 값을 갱신해준다.

여기서 A 아이템만을 더 사용했을 때 나머지가 없는지 확인하는 과정을 계속한다.

 

끝까지 답이 나오지 않을 경우에는 나눠지지 않는 케이스이므로 -1 를 return 해준다.

 

DP를 사용해서 풀라고 가이드가 되어 있던 것 같은데 ..? 어떻게 해야하지 하다가 DP로 푼건 아니고 그냥 푼 것 같다..

 

 

문제 12. 발전기

let N;
let result = 0;
const village = [];

rl.on('close', () => {
	const install = () => {
		while (queue.length) {
			let queuePop = queue.pop(0)
			let queueI = queuePop[0]
			let queueJ = queuePop[1]
			if (village[queueI][queueJ] === "1") {
				village[queueI][queueJ] = "0"
			}
			dir.map((d) => {
				nextI = queueI + d[0]
				nextJ = queueJ + d[1]
				if (nextI < 0 || nextI >= N || nextJ < 0 || nextJ >= N) return;
				if (village[nextI][nextJ] === "1") queue.push([nextI, nextJ]);
			})
		}
	}
	
	const queue = [];
	const dir = [[0, 1], [0, -1], [1, 0], [-1, 0]];
	for (let i=0; i<N; i++) {
		for (let j=0; j<N; j++) {
			if (village[i][j] === "1") {
				result++;
				queue.push([i, j]);
				install()
			}
		}
	}
	console.log(result)
})

큐를 사용해서 잘 기억나지 않는 BFS 개념을 끄집어.. 풀어 봤다.

village가 "1" 이면 그 때 발전기를 하나 설치하고(result++), 

queue에 해당 좌표값을 넣어 install 함수로 들어간다. (발전기를 이미 설치 했으니 install 이라는 네이밍은 맞지 않는 것 같기도..)

 

queue 길이만큼 while문을 도는데

현재 좌표 값이 1이면 0으로 바꿔 준 다음

해당 좌표의 상하좌우 값을 보면서 다음 집도 1이라면 queue에 좌표값을 넣어 다시 확인하게 한다.

그렇다면 queue를 돌면서 인접한 집을 모두 0으로 바꿔준다.

 

함수 동작이 끝나고 나면 연결되어있지 않던 집을 찾아서 다음 좌표를 queue에 넣고 또 반복한다.

최종 result를 출력하면 최소 갯수의 발전기 설치 갯수를 얻게 된다.

 

 

.. 아직 주 초기라 금방 풀었다 희히