[백준/BOJ] 1418번 : K-세준수 (JAVA / 자바)

안녕하세요~ 코딩하는 코알못 코메인입니다.

 

 

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

1418번: K-세준수

---

- 문제 -

 

난이도 브론즈 1 문제이다.

자바에서 입력방식은 scanner와 bufferedreader가 있다.

자바를 초반에 접하면 처음에 배우는 입력은 scanner이다. scanner가 bufferedreader보다 편하지만 속도가 느리다.

bufferedreader는 무조건 문자열로 받아오기때문에 정수형이나 실수형 변수에 저장하기 위해서는 입력과 형변환을 해줘야한다.

더 자세한 내용은 아래 글 참고 하면 좋다.

https://comain.tistory.com/3

(JAVA / 자바) Scanner 와 Bufferedreader

 

풀이 방법

문제자체는 쉽기때문에 구현 방법 위주로 보겠다.(한가지 볼 것은 1은 소수가 아니기때문에 인수를 1만 갖는 1은 조건에 안맞다 보는데 문제결과를 보면 1도 포함하고 있다. 그러니 1도 고려해서 풀자)

 두가지 방법으로 풀었다.(첫번째 방법은 직접 푼 방법이고, 두번째 방법은 더 나은 방법을 찾다가 다른 사람이 한걸 참고해서 푼 것이다.)

첫번째 방법 : 주어진 값이 100과 10이면 10이상의 값들 중 10이상의 소수의 배수들의 개수를 100에서 빼주는 것이다. 하지만 중복 없이 지우게 하려면 그만큼 반복문이 많이 돌아야해서 시간 초과가 나온다. 그래서 에라토스테네스의 체를 사용해 풀었다. 자세한 건 코드로 보자.

 

두번째 방법 : 주어진 값이 100과 10이면 1부터 100까지 해당 수들을 2부터 자신의 루트값까지의 정수로 나눈다. 그렇게 나눴을떄 나누어 떨어지는 수가 나오면 같은 수로 나누어 떨어지지 않을때까지 나누고, 나누어 떨어지지 않으면 나누는 값에 +1을 해서 마저 나눠주기를 반복한다. 그렇게 나눠서 나온 수들은 소수가 된다.

 

예를 들어 보자. 100과 10이 입력되었고, 이번에 계산할 값이 28이라면 우선 루트값을 보자. 5.291...이 될 것이다. 그럼 5까지 나눠주면 된다. 2부터 나눠준다. 2로 나누어 떨어지니 2로 나눈다. 그렇다면 14가 될 것이고, 2로 또 나누어 떨어지는지 보자. 나누어떨어진다. 나누면 7이 된다. 2로 안나누어 떨어진다. 이제 3 4 5를 보는데 7은 아무걸로도 나누어 떨어지지 않는다. 그렇다면 나온 소수는 2와 7이 된다. 만약 저 7이 1이 아니라면 7이 소인수중 제일 큰 값이 된다. 7은 10을 넘지 않기때문에 28은 조건에 맞는 수가 된다.

하나 더 보자. 50. 50의 루트는 7.07어쩌구이다. 그렇다면 나누는 값을 7까지 본다.

우선 2부터 본다. 2로 나눠진다. 25가된다. 2로 나눠지지 않는다.

3, 4 다 안나눠진다.

5보자. 5가 나온다. 5로 또 나눠진다. 1이 나온다.

1은 6,7로 안나눠떨어진다. 끝이다.

그럼 나온 소수는 2, 5이다. 최종적으로 나온 값은 1이다. 아까는 7이여서 7이 최댓값이였지만, 여기선 1이 나왔으니 이전 소수가 최댓값이 된다. 5이다. 5도 10 이하이기 때문에 조건에 맞는 값이다. 코드로 보자.

---

-풀이-

 

첫번째 방법

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

public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int K = Integer.parseInt(br.readLine());
		int count = 0;
        //조건에 맞는 값들을 구하기위한 배열
		int[] arr = new int[N + 1];
		
        //0이면 조건에 맞지않는 값, 1이면 조건에 맞는 값(우선 다 1대입,
        //0인덱스는 조건에 포함되지 않기 때문에 제외해도됨)
		for(int i = 1; i <= N; i++) {
			arr[i] = 1;
		}
		
		for(int i = (K + 1); i <= N; i++) {
        //소수인지 판별하기 위한 변수
			boolean decimal = true;
			for(int j = 2; j < i; j++) {
            //실수가 아니면 decimal에 false 저장하고 이미 소수가 아니니 반복문 종료
				if(i % j == 0) {
					decimal = false;
					break;
				}
			}
			//decimal이 true면 실수이기 때문에 해당 값의 배수들의 배열 위치에 0대입
			if(decimal == true) {
				int j = 1;
				while(true) {
					if((i * j) > N) break;
					arr[i * j] = 0;
					j++;
				}
			}
		}
        //조건에 맞는 값은 1이기때문에 1이 들어간 값의 개수를 구함
		for(int i = 1; i <= N; i++) {
			if(arr[i] == 1) count++;
		}
		System.out.println(count);
	}

}

 

두번째 방법

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

public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int K = Integer.parseInt(br.readLine());
		int count = 0;
		
		for(int i = 1; i <= N; i++) {
			int now = i;
			int max = 0;
			//현재 나눌 값인 i의 루트 값(Math.sqrt)이하 정수로 연산
			for(int j = 2; j <= Math.sqrt(i);) {
				//나누어떨어진면 같으 값으면 나누어떨어지지 않을때까지 연산
				if(now % j == 0) {
					now /= j;
					max = j;
				//나누어떨어지지 않으면 j +1
				}else {
					j++;
				}
			}
			//해당 반복문이 끝나면 최종 값이 1이 아니면 현재 값을 최댓값에 저장
			if(now != 1) max = now;
			//최댓값이 K보다 작거나 같으면 조건에 맞는 값이다.
			if(max <= K) count++;
		}
		System.out.println(count);
	}

}

---

-결과-

 

첫번째 방법

두번째 방법

이정도 문제에서도 많이 헤맨거보면 멀고도 멀었다는 생각이 들뿐이다...

---

아직 코딩 공부가 부족한 필자라 설명과 풀이 방법이 많이 미흡할 수 있다. 코딩 고수분들은 보시고 문제점이 있다면 댓글로 말해주시면 감사한 마음으로 참고 수정 하겠습니다.