12. 박 터뜨리기(19939)
문제
K개의 팀이 박 터트리기 게임을 한다. 각 팀은 하나의 바구니를 가지고 있고, 바구니에 들어있는 공을 던져서 자기 팀의 박을 터트려야 한다.
우리는 게임을 준비하기 위해서, N개의 공을 K개의 바구니에 나눠 담아야 한다. 이때, 게임의 재미를 위해서 바구니에 담기는 공의 개수를 모두 다르게 하고 싶다. 즉, N개의 공을 K개의 바구니에 빠짐없이 나누어 담는데, 각 바구니에는 1개 이상의 공이 있어야 하고, 바구니에 담긴 공의 개수가 모두 달라야 한다.
게임의 불공정함을 줄이기 위해서, 가장 많이 담긴 바구니와 가장 적게 담긴 바구니의 공의 개수 차이가 최소가 되도록 담을 것이다.
공을 바구니에 나눠 담기 위한 규칙을 정리하면 다음과 같다.
- N개의 공을 K개의 바구니에 빠짐없이 나누어 담는다.
- 각 바구니에는 1개 이상의 공이 들어 있어야 한다.
- 각 바구니에 담긴 공의 개수는 모두 달라야 한다.
- 가장 많이 담긴 바구니와 가장 적게 담긴 바구니의 공의 개수 차이가 최소가 되어야 한다.
위의 규칙을 모두 만족하며 N개의 공을 K개의 바구니에 나눠 담을 때, 나눠 담을 수 있는지 여부를 결정하고, 담을 수 있는 경우에는 가장 많이 담긴 바구니와 가장 적게 담긴 바구니의 공의 개수 차이를 계산해서 출력하는 프로그램을 작성하시오.
입력
첫 번째 줄에 공의 개수를 나타내는 N과 팀의 수를 나타내는 정수 K가 주어진다.
출력
N개의 공을 K개의 바구니에 문제의 규칙을 만족하면서 나눠 담을 수 있다면, 가장 많이 담긴 바구니와 가장 적게 담긴 바구니의 공의 개수 차이를 출력한다. 나눠 담을 수 없는 경우에는 -1을 출력한다.
작성한 코드
let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().split("\n");
let [n, k] = input[0].split(" ").map(Number); // n: 공의 개수, k: 팀의 수
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);
}풀이
- 가장 많이 담긴 바구니와 가장 적게 담긴 바구니의 공의 개수 차이가 최소가 되려면 공의 개수가 최대한 연속적이게 만들어야 함!
- N = 15, K = 5일 때, 공의 개수를 1, 2, 3, 4, 5로 나누어 준다
- N = 16, K = 5일 때, 공의 개수를 1, 2, 3, 4, 6로 나누어 준다
- N = 17, K = 5일 때, 공의 개수를 1, 2, 3, 5, 6로 나누어 준다
- 정답은 K-1 혹은 K
- N이 너무 작으면 안됨 → 1 + … + K ≤ N
13. 회문(17609)
문제
회문(回文) 또는 팰린드롬(palindrome)은 앞 뒤 방향으로 볼 때 같은 순서의 문자로 구성된 문자열을 말한다. 예를 들어 ‘abba’ ‘kayak’, ‘reviver’, ‘madam’은 모두 회문이다. 만일 그 자체는 회문이 아니지만 한 문자를 삭제하여 회문으로 만들 수 있는 문자열이라면 우리는 이런 문자열을 “유사회문”(pseudo palindrome)이라고 부른다. 예를 들어 ‘summuus’는 5번째나 혹은 6번째 문자 ‘u’를 제거하여 ‘summus’인 회문이 되므로 유사회문이다.
여러분은 제시된 문자열을 분석하여 그것이 그 자체로 회문인지, 또는 한 문자를 삭제하면 회문이 되는 “유사회문”인지, 아니면 회문이나 유사회문도 아닌 일반 문자열인지를 판단해야 한다. 만일 문자열 그 자체로 회문이면 0, 유사회문이면 1, 그 외는 2를 출력해야 한다.
입력
입력의 첫 줄에는 주어지는 문자열의 개수를 나타내는 정수 T(1 ≤ T ≤ 30)가 주어진다. 다음 줄부터 T개의 줄에 걸쳐 한 줄에 하나의 문자열이 입력으로 주어진다. 주어지는 문자열의 길이는 3 이상 100,000 이하이고, 영문 알파벳 소문자로만 이루어져 있다.
출력
각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다.
작성한 코드
let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().split("\n");
let t = Number(input[0]); // 문자열의 개수 T (1<=T<=30)
// 회문인지 확인
function palindrome(x) {
// 문자열을 뒤집은 것과 동일한지 확인
return x === x.split("").reverse().join("");
}
for (let line = 1; line <= t; line++) {
let str = input[line];
if (palindrome(str)) console.log(0); // 회문인 경우
// 회문이 아닌 경우, 유사 회문인지 검사
else {
let found = false;
let n = str.length; // 문자열의 길이
for (let i = 0; i < parseInt(n / 2); i++) {
// 대칭이 아닌 인덱스 찾은 경우
if (str[i] != str[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); // 회문도 유사 회문도 아닌 경우
}
}풀이
유사 회문: 한 문자를 삭제하여 회문으로 만들 수 있는 문자열
- 문자열의 앞에서부터 한 문자씩 확인하며 회문이 성립하는지 확인
- 만약, 회문이 성립하지 않는 위치를 찾는다면 유사 회문이 가능한지 여부 판단
-
해당 문자를 지웠을 때 유사회문이 될 수 있는지 확인
-
대칭된 위치에 있는 문자를 지웠을 때 유사회문이 될 수 있는지 확인
-
14. 박스 채우기(1493) ⭐️ 다시 풀기 ⭐️
문제
세준이는 length × width × height 크기의 박스를 가지고 있다. 그리고 세준이는 이 박스를 큐브를 이용해서 채우려고 한다. 큐브는 정육면체 모양이며, 한 변의 길이는 2의 제곱꼴이다. (1×1×1, 2×2×2, 4×4×4, 8×8×8, ...)
세준이가 가지고 있는 박스의 종류와 큐브의 종류와 개수가 주어졌을 때, 박스를 채우는데 필요한 큐브의 최소 개수를 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 세 자연수 length width height가 주어진다.
둘째 줄에 세준이가 가지고 있는 큐브의 종류의 개수 N이 주어진다.
셋째 줄부터 총 N개의 줄에 큐브의 종류 Ai와 개수 Bi가 i가 증가하는 순서대로 주어진다. 큐브의 종류는 한 변의 길이를 나타낼 때 쓰는 2i에서 i이다.
출력
첫째 줄에 필요한 큐브의 개수의 최솟값을 출력한다. 만약 채울 수 없다면 -1을 출력한다.
작성한 코드
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, width, height] = input[0].split(" ").map(Number);
let cubes = Array(20).fill(0);
let n = Number(input[1]);
for (let i = 2; i <= n + 1; i++) {
let [a, b] = input[i].split(" ").map(Number);
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); // 박스를 가득 채우지 못한 경우풀이
- 큐브의 길이, 너비, 높이는 항상 2의 제곱 형태
- 큰 큐브는 항상 자기보다 작은 큐브로 채울 수 있음
- 큰 큐브부터 차근차근 채워 나가면 해결 가능
- ‘거스름 돈’ 문제와 유사
