문제
상근이는 오락실에서 바구니를 옮기는 오래된 게임을 한다. 스크린은 N칸으로 나누어져 있다. 스크린의 아래쪽에는 M칸을 차지하는 바구니가 있다. (M<N) 플레이어는 게임을 하는 중에 바구니를 왼쪽이나 오른쪽으로 이동할 수 있다. 하지만, 바구니는 스크린의 경계를 넘어가면 안 된다. 가장 처음에 바구니는 왼쪽 M칸을 차지하고 있다.
스크린의 위에서 사과 여러 개가 떨어진다. 각 사과는 N칸중 한 칸의 상단에서 떨어지기 시작하며, 스크린의 바닥에 닿을때까지 직선으로 떨어진다. 한 사과가 바닥에 닿는 즉시, 다른 사과가 떨어지기 시작한다.
바구니가 사과가 떨어지는 칸을 차지하고 있다면, 바구니는 그 사과가 바닥에 닿을 때, 사과를 담을 수 있다. 상근이는 사과를 모두 담으려고 한다. 이때, 바구니의 이동 거리의 최솟값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N과 M이 주어진다. (1 ≤ M < N ≤ 10) 둘째 줄에 떨어지는 사과의 개수 J가 주어진다. (1 ≤ J ≤ 20) 다음 J개 줄에는 사과가 떨어지는 위치가 순서대로 주어진다.
출력
모든 사과를 담기 위해서 바구니가 이동해야 하는 거리의 최솟값을 출력한다.
입출력 예시
-
입력
5 1
3
1
5
3 -
출력
6
-
입력
5 2
3
1
5
3 -
출력
4
소스 코드
const fs = require('fs');
const input = fs.readFileSync("./dev/stdin").toString().trim().split('\n');
const [N,M] = input[0].split(' ').map(a=>Number(a)) // N : 스크린, M : 바구니 길이
const apple_num = Number(input[1]) // 사과의 갯수
const apples = input.slice(2,input.length).map(a=> Number(a))
// input의 인덱스 2번부터 input 길이 미만의 인덱스 번호까지 배열로 뽑아낸다.
let answer = 0
let start = 1 // 바구니의 첫 부분
let end = M // 바구니의 마지막 부분
// for..of
// 반복가능한 객체에 대해서 반복하는 루프 생성
// 즉 apples의 길이 만큼 for문을 돌고 apples를 돌 때 해당 요소는 apple
// map과 유사한 매커니즘. 결과값은 아예 다름
for(let apple of apples){
if (end < apple){
answer += apple - end
end = apple
start = apple - (M - 1)
}
else if (start > apple){
answer += start - apple
start = apple
end = apple + (M - 1)
}
}
console.log(answer)소스 코드 2
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "BOJ/input.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");
// .trim()을 안해줘서 틀렸다......
let basket = Number(input[0].toString().split(" ")[1]);
let move = Number(0); // 움직인 횟수
let start = Number(1);
let end = basket;
for (var i = 2; i < input.length; i++) {
if (Number(input[i]) < start || Number(input[i]) > end) {
if(Number(input[i]) < start) {
move += (start - Number(input[i]));
end -= (start - Number(input[i]))
start = Number(input[i]);
} else if (Number(input[i]) > end) {
move += (Number(input[i]) - end);
start += (Number(input[i]) - end);
end = Number(input[i]);
}
}
}
console.log(move);느낀점
구선생님 + 맞은 분의 코드를 참고하여 작성할 수 있었다...
해당 문제는 그리디 알고리즘 을 이용한 문제이다. 그리디 알고리즘의 핵심은 적은 활동으로 최대한의 이득을 보는 것이다.
그리디 알고리즘의 지식도 미약했고, 요즘 코테 문제 잘 풀린다고 실버 문제에 도전했다가 아주 크게 데였다...🔥
문제 접근의 핵심은
최소로 움직이려면 바구니의 끝부분으로 사과를 받아야 한다
이다.
start는 바구니의 첫 부분, end는 바구니의 마지막 부분에 해당한다. 사과를 받을 경우를 3가지로 나눌 수 있다.
- 사과가 떨어지는 위치가 start, end 사이다.
- 사과가 떨어지는 위치가 바구니의 첫 부분보다 앞쪽에 떨어진다
- 사과가 떨어지는 위치가 바구니의 마지막 부분보다 뒷쪽에 떨어진다.
1번의 경우 바구니를 움직일 필요가 없다.
2번의 경우 (바구니 첫 부분 - 사과가 떨어지는 위치) 만큼 이동하고,
바구니의 첫 부분은 사과가 떨어지는 위치로
바구니의 마지막 부분은 (사과가 떨어지는 위치 + (바구니 길이 - 1)) 또는 원래 있던 위치 - (바구니가 이동한 횟수) 로 갈 것이다.
3번의 경우 (사과가 떨어지는 위치 - 바구니 마지막 부분) 만큼 이동하고,
바구니의 첫 부분은 (사과가 떨어지는 위치 - (바구니 길이 - 1)) 또는 원래 있던 위치 + (바구니가 이동한 횟수) 로 갈 것이다.
바구니의 마지막 부분은 사과가 떨어지는 위치로 갈 것이다.
코테 문제 잘 풀린다고 자만하지 말고 지식을 습득하면서 단계를 높혀나가자🔥
