[백준] 20952. 게임 개발자 승희

문제 링크

[백준] 20952. 게임 개발자 승희

풀이 과정

배열 A 에 1을 더했을 때, 3을 더했을 때, 6을 더했을 때의 모습은 위와 같습니다.

• 배열 A 각 원소에 1을 더해서 만들어지는 수 중 7이 되는 수는 배열 A의 6입니다. (6 → 7)
• 1을 더한 배열 각 원소에 2를 더해 만들어지는 수 중 7이 되는 수는 배열 A의 4입니다. (4 → 5 → 7)
• 2를 더한 배열 각 원소에 3을 더해 만들어지는 수 중 7이 되는 수는 배열 A의 1입니다. ( 1 → 2 → 4→ 7)

각 누적합 sum 에 대해 걸러지는 수 6, 5, 1 을 구하는 수식을 나타내면 (7 - (sum % 7)) % 7 이 됩니다.

• sum이 1일 때 : (7 - (1 % 7)) % 7 = 6
• sum이 3일 때 : (7 - (3 % 7)) % 7 = 4
• sum이 6일 때 : (7 - (6 % 7)) % 7 = 1

배열 A의 모든 수를 7로 나눈 나머지를 이용해 표시함으로써, 모든 숫자를 단 7개의 요소를 통해 체크합니다. 예를 들어, remain[0] 이 true 면, 배열 A에는 7로 나누어 떨어지는 숫자가 있음을 의미하게 됩니다.

누적합이 1일 때, 즉 배열 A에 배열 B의 첫 번째 원소 1만 더했을 때의 7의 배수가 되는 숫자를 확인합니다. 위에 구한 수식에 따라, 누적합이 1일 때 걸러지는 수는 6입니다. 이는 7로 나누었을 때 나머지가 6인 6, 13, 20 등을 의미합니다. 해당 숫자가 존재하므로 false 처리합니다.

누적합이 3일 때, 즉 배열 A에 배열 B의 첫 번째 원소를 더한 결과에 다시 2를 더했을 때 7의 배수가 되는 숫자를 확인합니다. 위에 구한 수식에 따라, 누적합이 3일 때 걸러지는 수는 4입니다. 이는 7로 나누었을 때 나머지가 4인 4, 11, 18 등을 의미합니다. 해당 숫자가 존재하므로 false 처리합니다.

누적합이 6일 때, 즉 배열 A에 배열 B의 첫 번째 원소를 더한 결과에 2를 더하고, 이후 3을 더했을 때 7의 배수가 되는 숫자를 확인합니다. 위에 구한 수식에 따라, 누적합이 6일 때 걸러지는 수는 1입니다. 이는 7로 나누었을 때 나머지가 1인 1, 8, 15 등을 의미합니다. 해당 숫자가 존재하므로 false 처리합니다.

최종 누적합으로 걸러진 remain 배열을 확인하며, 배열 A의 수가 아직까지 살아남았다면, 해당 값에 최종 누적합 6을 의미하는 sum 을 더한 값을 기록합니다.

코드

const fs = require("fs");
const stdin = (process.platform === "linux"
    ? fs.readFileSync("/dev/stdin")
    : `7 3
1 2 3 4 5 6 7
1 2 3`
)
    .toString()
    .trim()
    .split("\n");
const input = (() => {
    let line = 0;
    return () => stdin[line++];
})();

const [N, M] = input().split(" ").map(Number);
const A = input().split(" ").map(Number);
const B = input().split(" ").map(Number);
let remain = Array(7).fill(false);
let remainCnt = 0;

for (let num of A) {
    let matchingIdx = num % 7;

    if (!remain[matchingIdx]) {
        remain[matchingIdx] = true;
        remainCnt++;
    }
}

let sum = 0;

for (let num of B) {
    sum += num;
    let target = (7 - (sum % 7)) % 7;

    if (!remain[target]) continue;
    if (remainCnt == 1) {
        sum -= num;
        continue;
    }

    remain[target] = false;
    remainCnt--;
}

let answer = [];

for (let num of A) {
    let matchingIdx = num % 7;

    if (remain[matchingIdx]) {
        answer.push((num + sum) % (1e9 + 7));
    }
}

console.log(answer.length);
console.log(answer.join(" "));