[STUDY] 탐욕 알고리즘 문제풀이 4 230905

~58일차~

1. 박 터트리기

https://www.acmicpc.net/problem/19939

강의에서 제시한 문제 해결 아이디어

• 가장 많이 담긴 바구니와 가장 적게 담긴 바구니의 공의 개수 차이가 최소가 되려면?
  -> 공의 개수가 최대한 연속적이게
• 항상 정답은 K-1 혹은 K

제출 답안

let fs = require('fs');
let input = fs.readFileSync('dev/stdin').toString().split('\n');

//n개의 공, k개의 바구니
let [n, k] = input[0].split(' ').map(Number);

let sum = [];
for (let i = 1; i < k+1; i++) { //연속적으로 수를 더하고 배열에 넣기
  sum.push(i);
}

// 연속적인 합의 값 더하기
let newSum = [...sum].reduce((prev, curr) => prev + curr);

//공의 개수와 비교
newSum==n
? console.log(sum[sum.length - 1]-1)
: console.log(-1)

-오답 - vs는 정상 출력되었는데 이번에도 백준은 오답.
아마 올바른 그리디로 하지 않아서가 문제인 것 같다.

정답 예시

let fs = require('fs');
let input = fs.readFileSync('dev/stdin').toString().split('\n');

let n = Number(input[0].split(' ')[0]);
let k = Number(input[0].split(' ')[1]);

let summary = 0; // 1부터 k까지의 합
for (let i = 1; i < k+1; i++) { 
  summary += i;
}
if (summary > n) { // 공의 개수 부족
  console.log(-1);
}
else { // 공의 개수 충분
  n -= summary;
  if(n % k == 0) console.log(k-1); //k개에 각각 1씩 더하기
  else console.log(k);
}

2. 회문

https://www.acmicpc.net/problem/17609

강의에서 제시한 문제 해결 아이디어

• 유사회문 : 한 문자를 삭제하여 회문으로 만들 수 있는 문자열
• 문자열의 앞에서부터 한 문자씩 확인하면서 회문이 성립하는지 확인
• 성립하지 않는 위치를 찾는다면 다음의 과정으로 유사회문이 가능한지 여부 판별
  1. 해당 문자를 지웠을 때 가능한지
  2. 대칭된 위치에 있는 문자를 지웠을 때 가능한지

제출 답안

let fs = require('fs');
let input = fs.readFileSync('dev/stdin').toString().split('\n');

//문자열 개수
let t = Number(input[0]);
//문자열
let arr = [];
for(let i = 1; i <=n; i++) arr.push(input[i]);

//1. 회문인지 0
//2. 유사회문 1
//3. 둘다 아닌지 2

for (let text of arr) {
  // 문자열 비교
  for (let j = 1; j <parseInt(text.length/2); j++)
  if (text[j-1] == text[text.length-1-j]) console.log(0) //회문일 때 0
  else if (text[j-1] !== text[text.length-1-j]) {
    // 해당원소 제거 or 반대편 원소 제거
  }
}

-오답 : 미제출
원소 제거 코드 구현을 하지 못했다.

정답 예시

let fs = require('fs');
let input = fs.readFileSync('dev/stdin').toString().split('\n');

function palindrome(x) {
  return x == x.split('').reverse().join('');
}

let testCases = Number(input[0]);
for (let tc = 1; tc <=testCases; tc++) { //문자열 입력받기
  let data = input[tc];
  if (palindrome(data)) console.log(0); // 회문인 경우
 else {
  let found = false;
  let n = data.length; // 문자열 길이
  for (let i = 0; i < parseInt(n / 2); i++) {
    if (data[i] != data[n - i - 1]) { //대칭 아닌 인덱스 찾은 경우
    //앞쪽의 해당 원소 제거 후 회문 검사
    if(palindrome(data.slice(0, i) + data.slice(i+1,n))) found = true; //해당원소 기준으로 앞뒤문자만 붙임
    //앞쪽의 해당 원소 제거 후 회문 검사
    if(palindrome(data.slice(0, n - i - 1) + data.slice(n - i, n))) found = true;
    break;
    }
  }
  if(found) console.log(1); //유사 회문
  else console.log(2); //둘다 아님
  }
}

-> 정답 예시도 런타임 에러가 나서 다시 수정해볼 예정

3. 박스 채우기

https://www.acmicpc.net/problem/1493

강의에서 제시한 문제 해결 아이디어

• 큐브의 길이, 너비, 높이는 항상 2의 제곱 형태를 보임
• 큰 큐브는 항상 자기보다 작은 큐브로 채울 수 있다.
  -> 큰 큐브부터 채워나가면 해결 할 수 있다.

제출 답안

-오답 : 미제출

정답 예시

let fs = require('fs');
let input = fs.readFileSync('dev/stdin').toString().split('\n');


//x보다 작거나 같으면서 가장 가까운 2^i를 찾는 함수
function nearestSquare(x) {
  let i = 1;
  while (( 2 ** i) <= x) i += 1;
  return i - 1;
}


let length = Number(input[0].split(' ')[0]);
let width = Number(input[0].split(' ')[1]);
let height = Number(input[0].split(' ')[2]);
let cubes = Array(20).fill(0);

let n = Number(input[1]);
for(let i = 2; i <=n +1; i++) {
  let a = Number(input[i].split(' ')[0]);
  let b = Number(input[i].split(' ')[1]);
  cubes[a] = b;
}

let size = 19;
size = nearestSquare(length);
size = Math.min(size, nearestSquare(width));
size = Math.min(size, nearestSquare(height));

let res = 0;
let used = 0;

for (let i = size; i >= 0; i--) {
  used *= 8; // 채널, 너비, 높이가 2씩 줄었으므로 큐브의 개수는 8배 증가
  cur = (2 ** i); //현재의 정육면체 큐브의 길이
  //채워넣어야 할 큐브의 개수 계산
  let required = parseInt(length /cur)
    * parseInt(width /cur)
    * parseInt(height /cur)
    - used;

  let usage = Math.min(required, cubes[i]); // 이번 단계에서 넣을 수 있는 큐브의 개수
  res += usage;
  used += usage; 
}

if (used == length * width * height) console.log(res); //박스를 가득 채운 경우
else console.log(-1) // 박스를 가득 채우지 못한 경우