4. 설탕 배달(2839)
문제
상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다.
상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다.
상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다. (3 ≤ N ≤ 5000)
출력
상근이가 배달하는 봉지의 최소 개수를 출력한다. 만약, 정확하게 N킬로그램을 만들 수 없다면 -1을 출력한다.
작성한 코드
let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().split("\n");
let n = Number(input[0]); // 배달해야 할 설탕 무게 n
let fiveKilo = parseInt(n / 5);
let threeKilo = 0;
let restSugar = n % 5;
let answer = 0;
while (true) {
// 5kg의 개수가 0이거나 남은 설탕의 무게가 3의 배수 인 경우 중단
if (fiveKilo === 0 || restSugar % 3 == 0) break;
fiveKilo -= 1; // 5kg의 개수 줄여 나가기
restSugar = n - 5 * fiveKilo; // 남은 설탕 재정의
}
// 남은 설탕을 3으로 나눈 나머지가 3의 배수 인 경우에만 3kg 봉지 카운트
if (restSugar % 3 === 0) threeKilo = parseInt(restSugar / 3);
// 정확하게 N킬로그램 만들수 없는 경우 -1 반환
if (threeKilo === 0 && fiveKilo === 0) answer = -1;
else answer = fiveKilo + threeKilo; // N킬로그램을 만드는 총 봉지 개수
console.log(answer);풀이
- 5kg을 많이 뺄 수 있을 때까지 카운트 후 3kg 빼기
5. A→B(16953)
문제
정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다.
- 2를 곱한다.
- 1을 수의 가장 오른쪽에 추가한다.
A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.
입력
첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다.
출력
A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값을 출력한다. 만들 수 없는 경우에는 -1을 출력한다.
작성한 코드
let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().split("\n");
let [a, b] = input[0].split(" ").map(Number);
let cnt = 0;
// b가 a와 같거나 작아질때까지 반복
while (b > a) {
// 2로 나누어 떨어지는 경우 2로 나누기
if (b % 2 === 0) b /= 2;
// 아닌 경우, 맨 뒤 1 제거
else {
let str = String(b); // b를 문자열로 변환
// 맨 뒤가 1인 경우 1 제거
if (str.charAt(str.length - 1) === "1") {
str = str.slice(0, -1);
b = Number(str);
} else break; // 1이 아닌 경우 반복문 중단
}
cnt += 1;
}
let answer = 0;
if (b !== a) answer = -1; // b가 a와 같지 않은 경우 만들 수 없으므로 -1 반환
else answer = cnt + 1; // 연산 횟수 + 1
console.log(answer);풀이
- B에서 A로 이동
- 먼저, 2로 나누어 떨어지는지 확인
- 2로 나누어 떨어지지 않는 경우 맨 마지막 문자열에 1인지 확인
- 2로 나누어 떨어지지도 않고, 맨 마지막 문자열이 1도 아닌 경우 더 이상 이동 불가능
6. 수들의 합(1789)
문제
서로 다른 N개의 자연수의 합이 S라고 한다. S를 알 때, 자연수 N의 최댓값은 얼마일까?
입력
첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다.
출력
첫째 줄에 자연수 N의 최댓값을 출력한다.
처음 작성한 코드 → 시간 초과
let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().split("\n");
let s = Number(input[0]); // 자연수의 합 S
let nList = []; // 서로 다른 n개의 리스트
let n = 1; // 1부터 시작
while (true) {
s -= n;
if (nList.includes(s) || s === 0) break; // 뺀 값이 nList에 존재하거나 s가 0인 경우 중단
nList.push(n); // n 포함
n += 1;
}
console.log(nList.length + 1); // 제일 큰 수 제외했으므로 1 더해주기풀이
- 1부터 시작해서 최대한 많은 n 구할 수 있도록 하기
- 만약, nList에 이미 존재하거나 s가 0인 경우 반복문 중단
- 하지만,,, 시간 초과 발생 ㅠㅠ
올바른 코드
let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().split("\n");
let s = Number(input[0]); // 자연수의 합 S
let sum = 0; // 누적 합
let current = 0; // 1부터 차례대로 더하며 증가
while (sum <= s) {
current += 1; // 1부터 증가
sum += current;
}
console.log(current - 1);풀이
- 가능한 작은 수부터 더하기
- 1부터 시작하여 차례대로 더하면서 합이 S를 넘어가지 않도록 하되, 최대한 많이 더하기
- 1부터 출발하여, 가능한 작은 개수로 S를 표현하면 되므로, 단순히 1부터 증가시켜가며 누적 합 계산
7. 신입사원(1946)
문제
언제나 최고만을 지향하는 굴지의 대기업 진영 주식회사가 신규 사원 채용을 실시한다. 인재 선발 시험은 1차 서류심사와 2차 면접시험으로 이루어진다. 최고만을 지향한다는 기업의 이념에 따라 그들은 최고의 인재들만을 사원으로 선발하고 싶어 한다.
그래서 진영 주식회사는, 다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다는 원칙을 세웠다. 즉, 어떤 지원자 A의 성적이 다른 어떤 지원자 B의 성적에 비해 서류 심사 결과와 면접 성적이 모두 떨어진다면 A는 결코 선발되지 않는다.
이러한 조건을 만족시키면서, 진영 주식회사가 이번 신규 사원 채용에서 선발할 수 있는 신입사원의 최대 인원수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성적, 면접 성적의 순위가 공백을 사이에 두고 한 줄에 주어진다. 두 성적 순위는 모두 1위부터 N위까지 동석차 없이 결정된다고 가정한다.
출력
각 테스트 케이스에 대해서 진영 주식회사가 선발할 수 있는 신입사원의 최대 인원수를 한 줄에 하나씩 출력한다.
작성한 코드
let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().split("\n");
let tc = Number(input[0]); // 테스트 케이스 개수
let line = 1;
while (tc--) {
let n = Number(input[line]); // 지원자 수
let scoreList = []; // 점수 [서류 등수, 면접 등수]
for (let i = 1; i <= n; i++) {
let data = input[line + i].split(" ").map(Number);
scoreList.push(data);
}
// 서류 등수를 기준으로 오름차순 정렬
scoreList.sort((a, b) => a[0] - b[0]);
let passCnt = 0; // 합격자 수
let minValue = 100001; // 최솟값
for (let [x, y] of scoreList) {
// 지금까지 봤던 면접 등수들 중 가장 작은 수이며 합격
if (y < minValue) {
minValue = y;
passCnt += 1;
}
}
console.log(passCnt);
line += n + 1; // 라인 변경
}풀이
- 서류 성적과 면접 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 사람만 합격
- [X: 서류, Y: 면접]
- X를 기준으로 오름 차순 정렬
- 차례대로 한 명씩 확인하며, 순위 Y가 현재까지 확인했던 Y 중 가장 작은 수라면 카운트
