BOJ_1418 : K-세준수

👉 문제링크

1418번: K-세준수

---

---

 

🔸 문제 분석 🔸

• 어떤 자연수의 소인수중 최대값이 K보다 크지 않으면 K-세준수이다.
• N이하의 자연수 중에 K-세준수의 개수를 구한다.

🔸 문제 풀이 🔸

• 1부터 N까지의 자연수들 각각 최대 소인수를 구하고, 그 값이 K를 넘는지 확인해야 한다.
  • 소인수 인지 확인하기 위해 자연수를 N까지 키워간다.
  • 현재 수가 소인수이면 그 수의 N보다 작은 배수들은 현재 수를 소인수 최대값으로 저장한다.(에라토스테네스의 체)
  • 만약 현재 수가 이전에 배수로 소인수를 구했으면 그 수와 K를 비교하고, 이전에 구한 값이 없으면 현재 수 자체가 소인수라는 것이며 이 값을 K와 비교한다.

🔸 코드 🔸

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int N = Integer.parseInt(br.readLine());
		int K = Integer.parseInt(br.readLine());

		int[] arr = new int[N + 1];
		int answer = 1;

		for (int i = 2; i <= N; i++) {
			if (arr[i] == 0) { // 자기 자신이 소인수
				if (i <= K)
					answer++;

				int temp = 2;
				while (i * temp <= N) {
					arr[i * temp] = i;
					temp++;
				}
			} else {
				if (arr[i] <= K)
					answer++;
			}
		}

		bw.write(Integer.toString(answer));
		bw.flush();
	}
}

🔸 코드 해석 🔸

• N과 K를 입력받고, N+1 크기의 int형 배열 arr를 선언한다.
• 현재 문제는 1을 소인수로 계산했으니, aswer의 초기값은 1이고 탐색도 2부터 시작한다.
• 2부터 N까지 인덱스를 늘려가며 각 수의 소인수 최대값을 구한다.
  • 현재 인덱스에 0이 저장되어있으면, 그 인덱스가 소인수 최대값이다.
    • 인덱스가 K이하라면 answer을 +1 한다.
    • N이하의 인덱스 배수에 인덱스를 저장한다. 임시로 소인수 최대값을 저장하는 것이다.
      에라토스테네스의 체가 적용되는 부분이다.
  • 현재 인덱스에 0이 아닌 값이 저장되어있으면, 그 저장된 수가 소인수 최대값이다.
    • 저장된 값이 K이하이면 answer을 +1한다.
• answer을 출력한다.

---

🔸 end 🔸

• 오랜만에 백준을 풀었더니 풀이 시간이 꽤 걸린 것 같다. 어서 재활을 마치고 골드 문제를 풀고싶다.
• 1은 사실 소수가 아니어서 소인수도 아닌데, 직접 예제 입력과 출력을 계산해보니 1을 정답에 포함하는 것 같아서 포함시켜서 풀 수 있었다.
  • 덕분에 문제를 잘못 이해한게 아닌가 걱정했는데, 그냥 불친절한 문제였다...
  • 다음은 예제를 계산해본 과정이다.