[BOJ] 1222 - 홍준 프로그래밍 대회 (Python, JavaScript)

 

 

아이디어

 

학생 수의 공약수와 그 공약수의 개수의 곱의 최댓값을 구한다.

 

 

풀이 #1 (Python)

 

2부터 값을 차례로 증가시키면서 현재 수와 현재 수의 배수가 되는 학생 수 개수 곱의 최댓값을 갱신해 나간다.

 

def solution():
    N = int(input())
    students = tuple(map(int, input().split()))
    M = max(students)
    multiples = [0]*(M+1)
    for student in students:
        multiples[student] += 1
    res = N
    for d in range(2, M+1):
        cnt = sum(multiples[d:M+1:d])
        if cnt > 1 and d*cnt > res:
            res = d*cnt
    print(res)

solution()

 

 

슬라이싱 대신 for문으로 최댓값을 구하는 코드는 PyPy3로 제출했을 때는 더 빠르지만 Python 3로 제출하면 더 느렸다.

# PyPy3 기준으로는 더 빠르나 Python 3 기준으로는 더 느린 코드
...
for d in range(1, M+1):
    for i in range(d*2, M+1, d):
        multiples[d] += multiples[i]
    if multiples[d] > 1 and d*multiples[d] > res:
        res = d*multiples[d]
...

 

 

 

풀이 #2 (JavaScript)

 

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

function solution() {
    const N = Number(input[0]);
    const students = input[1].split(' ').map(Number);
    M = Math.max(...students);
    let multiples = Array(M+1).fill(0);
    for (student of students) multiples[student]++;
    let res = N;
    for (let d=2; d<=M; d++) {
        let cnt = 0;
        for (let i=d; i<=M; i+=d) cnt += multiples[i];
        if (cnt > 1 && d*cnt > res) res = d*cnt;
    }
    console.log(res);
}

solution();