문제

https://programmers.co.kr/learn/courses/30/lessons/12921

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

public int solution(int n) {
    boolean[] prime = new boolean[n+1];

    prime[0] = true;
    prime[1] = true;

    for (int i = 2; (i * i) <= n; i++) {
        if (!prime[i]) {
            for (int j = i * 2; j <= n; j += i) {
                prime[j] = true;
            }
        }
    }

    int answer = 0;
    for (boolean is : prime) {
        if (!is) {
            answer++;
        }
    }

    return answer;
}

흐름

• 에라토스테네스의 체로 해결

1. n까지의 숫자중 0과 1은 소수가 아니므로 true 할당
2. 2부터 루트n 까지 반복하면서 배수들에 true 할당
3. 소수 판별한 배열 prime을 loop 돌면서 false 인 경우에만 갯수 추가
4. 끝

부연 설명

1

for (int i = 2; (i * i) <= n; i++)

입력받은 수 n이 합성수 인 경우 $$n = a * b​$$ 로 나타낼 수 있다.
이 때 a와 b 중 큰거나 같은 수를 a, 작거나 같은 수를 b라고 가정하면 b가 a보다 작으므로 $$ a * a >= a * b $$ 이고
$$ n = a * b $$ 이므로, 큰 수 a의 제곱일 경우 $$ a^2>=n $$ 처럼 된다.
이를 치환하면 $$ a>=\sqrt{n} $$ 이 되므로 a의 최솟값은 $$ \sqrt{n} $$ 이 된다.
그리고 b는 $$ a >= b $$이므로 b의 최댓값은 $$ \sqrt{n} $$ 이 된다.
고로 n이 소수가 아닌 합성수라면 a의 와 b의 합성수로 이루어 짐을 알 수 있으므로, $$ \sqrt{n} $$ 까지만 반복하면 소수임을 판별할 수 있다.

• ex) 입력받은 수 n이 50일 경우 $$ \sqrt{50} $$ = 7.071067811865475‬‬….이므로, 7.071067811865475‬‬… 을 기준으로 50의 약수 {1,2,5,10,25,50}을 나누면 b = {1, 2, 5}, a = {10, 25, 50} 이므로 b만 검사하면 50이 소수 인지 아닌지 알 수 있다.

1

for (int j = i * 2; j <= n; j += i)

원래는 i보다 작은 수인 경우 이미 이전에 작은 수 * i에서 삭제된 상태이므로 i * i인 게 맞으나,
i의 값이 너무 클 경우 문제가 될 수 있으므로 $$ i * 2 $$ 로 설정한다.
물론 이 문제에선 100만 까지로 한정되어 있으므로 $$ i * i $$ 를 해도 문제는 없다.

참고 사이트

• https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4
• https://blog.naver.com/loveshurt/221774410486
• https://makedotworld.tistory.com/13

댓글 공유

https://www.acmicpc.net/problem/11399

소스

1
2
3
4
5
6
7
8
9
10
11
12

public static int solution(int n, int[] times) {
    Arrays.sort(times);
    
    int answer = 0;
    for (int i = 0; i < times.length; i++) {
        answer += times[i] * (n-i);
    }
    
    return answer;
}

흐름

1. 시간이 짧게 걸리는 사람이 앞에 올수록 전체 수행 시간이 짧아지므로 sorting부터 실행

2. 앞에 사람이 걸리는 시간은 그 뒤 사람들도 그만큼 시간이 + 되는 것이므로 n-i 한 값을 곱함

   ex) 첫 번째 사람이 1분 걸리면 2, 3, 4, 5 번째 사람도 1분씩 더 걸리게 됨

3. 다 더한 값을 출력하면 끝

댓글 공유