PS#1 오늘의 PS
오늘도 Junah님이 맛있는 PS 한 상을 차려주셨다.
괄호(Gold4) #DP
Junah : DP라서 살짝 어려울 수도 있지만, DP는 사고할때 작은 정답이 모여서, 큰 정답을 만드는거니까. 작은 괄호에서 큰 괄호로 만들어지는 과정을 잘 생각해보면, 쉽게 풀지도?
풀이
풀고나니 Node.js로 제출된 풀이가 3개밖에 없었다.
해당 문제를 풀기 위한 포인트는 두 가지였다.
- 나열하면서 규칙을 추론하는 과정에서, 반드시 dp라는 특성을 이용할 수 있도록 이전 항을 온전히 사용할 수 있는 방법으로 경우의 수를 추론할 것.
- BigInt를 사용해서 계산할 것.
문제에 대한 점화식은 구했지만 25%에서 계속 WA가 발생했다.
원인은 BigInt였다. 연산하는 숫자의 뒤에 n을 붙여주면 BigInt로 바뀌게 된다.
25%에서 틀리는 선생님들은 BigInt로 연산하도록 하자.
const [_, ...input] = require("fs").readFileSync("/dev/stdin").toString().trim().split('\n').map(Number);
const LIMIT = 1000000007n;
let dp = Array(5001).fill(0n);
dp[0] = 1n;
dp[1] = 0n;
for (let i = 2; i <= 5000; i += 2) {
for (let j = 0; j < i; j += 2) {
dp[i] = (dp[i] + (dp[j] * dp[i - j - 2]) % LIMIT) % LIMIT;
}
}
dp = dp.map((v) => v ? v : 0n);
let answer = '';
for (let i of input) answer += `${dp[i]}\n`;
console.log(answer);수열(Silver3) #누적합 #sliding window
Junah : 풀다가 정 모르겠으면, 슬라이딩 윈도우로 검색해볼 것!
풀이1(누적합)
두 가지 풀이로 진행했다.
첫 풀이는 누적합을 캐싱한 뒤, 이를 이용해 최대값을 탐색하는 방법이었다.
const [order, temp] = require("fs").readFileSync("/dev/stdin").toString().trim().split('\n');
const [_, size] = order.split(' ').map(Number);
const arr = temp.split(' ').map(Number);
const cache = [];
cache[0] = 0;
for (let i = 1; i <= arr.length; i++) cache[i] = cache[i - 1] + arr[i - 1];
let max = Number.MIN_SAFE_INTEGER;
for (let i = 0; i <= arr.length - size; i++) max = Math.max(max, cache[i + size] - cache[i]);
console.log(max);이렇게 풀어놨더니 준아님이 맞는 풀이긴 한데, 슬라이딩 윈도우로 정석풀이 하라고 [ 갈 ] 하셔서 슬라이딩 윈도우로 다시 풀었다.😥
풀이2(sliding window)
const [order, temp] = require("fs").readFileSync("/dev/stdin").toString().trim().split('\n');
const [_, size] = order.split(' ').map(Number);
const arr = temp.split(' ').map(Number);
let window = [...arr].splice(0, size).reduce((acc, curr) => acc + curr);
let max = window;
for (let i = size; i <= arr.length - 1; i++) {
window = window + arr[i] - arr[i - size];
max = Math.max(max, window);
}
console.log(max);더 깔끔하긴 하다.
시간 차이를 확인해보자.
-
누적합
-
sliding window
Pengoose : 오.. 4ms면 시간차이 별로 없는데요..?
Junah : n이 커지면 차이가 더 커지겠죠?
인간-컴퓨터 상호작용(Silver1) #DP
Junah : 누적합 || DP
풀이
병렬적 누적합(?)같은 느낌으로 풀 수 있는 문제였다.
ASCII코드를 이용해 간단히 풀이하였다.
const [s, _, ...input] = require("fs").readFileSync("/dev/stdin").toString().trim().split('\n');
const cache = {}
for (let i = 97; i <= 122; i++) cache[i] = [0];
for (let i = 1; i <= s.length; i++) for (let j = 97; j <= 122; j++) j === s[i - 1].charCodeAt(0) ? cache[j][i] = cache[j][i - 1] + 1 : cache[j][i] = cache[j][i - 1];
let answer = '';
for (let i of input) {
const [target, ...rest] = i.split(' ');
const [start, end] = rest.map(Number);
const arr = cache[target.charCodeAt(0)];
answer += `${arr[end + 1] - arr[start]}\n`;
}
console.log(answer);연속합(Silver2) #누적합
Junah : 최대값을 구하는 방식이 누적합을 활용하긴하지만 살짝 테크닉이 들어간 문제
누적합이 마이너스라는 것의 의미를 이해하면 쉽게 풀 수 있을지도?
풀이
누적합을 할 때, 언제 끊을지 고민을 해본다면 금방 풀 수 있는 문제였다.
i - 1번 째의 누적합에 현재 number를 더했을 때, 0이하가 될 경우 누적합을 초기화하는 방식을 채택했다.
const [_, input] = require("fs").readFileSync("/dev/stdin").toString().trim().split('\n');
const nums = input.split(' ').map(Number);
const max = Math.max(...nums);
if (max < 0) console.log(max);
if (max >= 0) {
const cache = [nums[0]];
for (let i = 1; i <= nums.length - 1; i++) {
if (cache[i - 1] + nums[i] <= 0) {
cache[i] = 0;
continue;
}
cache[i] = cache[i - 1] + nums[i];
}
console.log(Math.max(...cache));
}회의실 배정(Silver1) #그리디
Junah : 정렬을 활용하되, 약간의 그리디 알고리즘이 들어감
웰노운 문제라서 티어가 낮은 감이 있지만, 객관적으로 좀 어려운 문제이니 계속 잡고 있지말고, 고민만 해볼 것
풀이
const [_, ...input] = require("fs").readFileSync("/dev/stdin").toString().trim().split('\n');
const arr = input.map((v) => v.split(' ').map(Number));
const sortedArr = arr.sort((a, b) => {
if (a[1] === b[1]) return a[0] - b[0];
return a[1] - b[1];
})
let answer = 1;
let [start, end] = sortedArr.shift();
for (let i of sortedArr) {
const [currS, currE] = i;
if (currS < end) continue;
[start, end] = [currS, currE];
answer++;
}
console.log(answer);
좌표 정렬하기(Silver5) #정렬
Junah : 내장함수 정렬을 이용하되, 비교 함수를 직접 넣어서 푸는 문제
풀이
간단하다. 그냥 내장함수 sort를 이용하여 요구사항에 맞게 정렬하면 된다.
const [_, ...input] = require("fs").readFileSync("/dev/stdin").toString().trim().split('\n');
const arr = input.map((v) => v.split(' ').map(Number));
const sortedArr = arr.sort((a, b) => {
if (a[0] === b[0]) return a[1] - b[1];
return a[0] - b[0];
})
let answer = '';
for (let i of sortedArr) answer += `${i.join(' ')}\n`;
console.log(answer);나이순 정렬(Silver5) #정렬
Junah : 내장함수 정렬을 이용하되, 비교함수를 직접 넣어서 푸는 문제
풀이
이전 문제와 동일하다. 그냥 구현문제다.
const [_, ...input] = require("fs").readFileSync("/dev/stdin").toString().trim().split('\n');
const answer = input.map((v) => v.split(' ')).sort((a, b) => Number(a[0]) - Number(b[0])).map((v) => v.join(' ')).join('\n');
console.log(answer);오늘도 잘먹었습니다 😙
