[백준]컨베이어 벨트 위의 로봇 20055 JS

·2023년 9월 6일
0

ProblemSolve

목록 보기
5/10

문제 링크

내 문제 풀이 빌드업

  1. n<=100이므로 시간 제한 1초 안에는 n^3까지 가능
    => 단순 구현 문제일 가능성 높음

  2. 자료구조 : 원형 리스트가 필요한가?
    => 어떻게 구현하는지도 잘 모르고 문제에서 로봇이 추가되는 지점과 로봇이 나가는 지점이 항상 일정하게 변함.
    즉 인덱스의 변화만으로 원형리스트처럼 배열로 풀이 가능

  3. 문제 해석이 어려워서 질문게시판을 여러번 정독함 ㅎ
    문제에서 설명하는 '과정'을 반복하면서 0의 개수가 K가 되면 종료

    시행착오

  • 문제의 '언제든지 로봇이 내리는 위치에 도달하면 그 즉시 내린다'를 제대로 생각하지 않고, 과정의 첫번째인 벨트가 회전할 때만 내리게 처리하는 실수를 했다.

    하지만 2번의 로봇이 칸을 이동할 때에도 내리는 위치로 이동하는 경우로 처리해줘야한다.

  • 처음엔 start와 end의 인덱스를 변화시키며 저장하였는데, 로봇이 내리는 위치인 mid가 필요하게 되서 다시 계산하는 불필요한 계산이 있었다. 사실 지금 풀이도 맞는 풀이인진 모르겠다

정답 풀이

const fs = require("fs");
let [n,k, ...arr] = fs.readFileSync("/dev/stdin")
 .toString()
 .trim()
 .split(/\s/)
 .map(Number)
let start = 0;
let mid = n - 1;
let count = 0;
// 각 단계 실행하기
let ans = 0
let box = Array.from({ length: 2 * n - 1 }, e => false)
while (count < k) {

 if (start == 0) start = 2 * n - 1
 else start--
 if (mid == 0) mid = 2 * n - 1
 else mid--
 //내리기
 box[mid] = false
 //  로봇 이동하기. curr에 갈 수 있는지 확인
 let curr = mid
 for (let i = 0; i < n; i++) {
   let before = curr === 0 ? 2 * n - 1 : curr - 1
   if (arr[curr] > 0 && !box[curr] && box[before]) {
     box[curr] = true
     arr[curr]--
     box[before] = false
     if (curr === mid) box[curr] = false
   }
   curr = before
 }
 //로봇 올리기
 if (!box[start] && arr[start] > 0) {
   box[start] = true
   arr[start]--
 }
 count = 0
 for (let i = 0; i < 2 * n; i++) {
   if (arr[i] === 0) count++
 }
 ans++
}
console.log(ans)

profile
중요한 건 꺾여도 다시 일어서는 마음

0개의 댓글