250x250
Notice
Recent Posts
Recent Comments
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 | 31 |
Tags
- 막내의막무가내 코틀린
- 안드로이드 sunflower
- Fragment
- 막내의막무가내 플러터 flutter
- 2022년 6월 일상
- 막내의 막무가내 알고리즘
- 안드로이드
- 막내의막무가내 목표 및 회고
- 막내의막무가내 rxjava
- 프로그래머스 알고리즘
- flutter network call
- 안드로이드 Sunflower 스터디
- 막내의막무가내 안드로이드 에러 해결
- 막내의막무가내 코볼 COBOL
- 막내의막무가내 코틀린 안드로이드
- 주택가 잠실새내
- 주엽역 생활맥주
- 부스트코스에이스
- 막내의막무가내
- 막내의막무가내 일상
- 막내의막무가내 프로그래밍
- 막무가내
- 막내의막무가내 SQL
- 막내의 막무가내
- 막내의막무가내 플러터
- 프래그먼트
- 막내의막무가내 안드로이드 코틀린
- 막내의막무가내 안드로이드
- 부스트코스
- 막내의막무가내 알고리즘
Archives
- Today
- Total
막내의 막무가내 프로그래밍 & 일상
[알고리즘] 백준 2023 신기한 소수 -백트랙킹- 자바 코틀린 본문
728x90
그동안 시간관계상 알고리즘 풀이를 못하였는데 약 두달만에 풀어봤네요. 오랜만의 풀이라 안그래도 없던 알고리즘 실력도 다 떨어졌는데 주요 알고리즘과 스탠다드한 문제 풀이로 감도 되찾고 실력을 쌓으려고합니다.. ㅎㅎ 시간 여유도 생겼으니 열심히 해야겠습니다.
youngest-programming.tistory.com/382
[알고리즘] 스터디 계획표
현재 하고있는것들이 있어 좀 밀렸지만 최대한 계획 맞춰서 공부
youngest-programming.tistory.com
예전 공부 계획표 참고하면서 분류당 한문제씩 풀어볼까 생각중입니다.
2023번: 신기한 소수
수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수
www.acmicpc.net
오늘은 백준 2023 신기한 소수 문제를 풀어봤습니다.
N자리수의 자연수들 중 1의자리부터 N자리까지 모두 소수인 자연수를 판별하는 문제로
소수랑 백트랙킹이 엮인 스탠다드한 문제였습니다.
처음 다음과 같이 에라토스테네스의 체로 최대 자리수의 소수판별 배열을 만들어서 풀이했는데 메모리 초과로 통과하지못하였습니다.
import java.util.Scanner;
class Main {
private static int N;
private static boolean[] prime;
private static StringBuilder sb = new StringBuilder();
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
int max = (int) Math.pow(10f, N); // N=2 -> 100
prime = new boolean[max];
makePrime(max);
dfs("", 0);
System.out.println(sb.toString());
}
private static void dfs(String num, int depth) {
if (depth == N) {
sb.append(num).append("\n");
return;
}
for (int i = 1; i <= 9; i++) {
int currentNum = Integer.parseInt(num + i);
if (!prime[currentNum]) {
dfs(currentNum + "", depth + 1);
}
}
}
private static void makePrime(int n) {
prime[0] = true;
prime[1] = true;
for (int i = 2; i <= Math.sqrt(n); i++) {
if (prime[i]) continue;
for (int j = i * i; j < prime.length; j += i) {
prime[j] = true;
}
}
}
}
그래서 소수판별방식을 그떄그떄 수를 매개변수로 받아서 판별하게 변경으로써 통과할 수 있었습니다.
풀이는 다음과 같습니다.
[Java]
import java.util.Scanner;
class Main {
private static int N;
private static StringBuilder sb = new StringBuilder();
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
dfs("", 0);
System.out.println(sb.toString());
}
private static void dfs(String num, int depth) {
if (depth == N) {
sb.append(num).append("\n");
return;
}
for (int i = 1; i <= 9; i++) {
int currentNum = Integer.parseInt(num + i);
if (isPrime(currentNum)) {
dfs(currentNum + "", depth + 1);
}
}
}
private static boolean isPrime(int n) {
// 0, 1
if (n < 2) return false;
// 2
if (n == 2) return true;
for (int i = 2; i < n; i++) {
// 소수 X
if (n % i == 0) return false;
}
return true;
}
}
[Kotlin]
import java.util.*
private var N = 0
private val sb = StringBuilder()
fun main(args: Array<String>) {
val sc = Scanner(System.`in`)
N = sc.nextInt()
dfs("", 0)
println(sb.toString())
}
private fun dfs(num: String, depth: Int) {
if (depth == N) {
sb.append(num).append("\n")
return
}
for (i in 1..9) {
val currentNum = (num + i).toInt()
if (isPrime(currentNum)) {
dfs(currentNum.toString() + "", depth + 1)
}
}
}
private fun isPrime(n: Int): Boolean {
if (n < 2) return false // 0, 1
// 2
if (n == 2) return true
for (i in 2 until n) { // 소수 X
if (n % i == 0) return false
}
return true
}
뎃글과 공감은 큰 힘이 됩니다. 감사합니다.!!
728x90
'알고리즘 > DFS, BFS, 시뮬, 백트래킹' 카테고리의 다른 글
[알고리즘] 백준 2146 다리만들기 -BFS- 자바 (0) | 2021.03.01 |
---|---|
[알고리즘] 백준 2468 안전영역 -BFS- 자바 (2) | 2021.02.28 |
[알고리즘] 프로그래머스 가장 먼 노드 -그래프- 자바 (0) | 2021.01.02 |
[알고리즘] 백준 1339 단어수학 -백트랙킹, 그리디- (0) | 2020.12.24 |
[알고리즘] 백준 13549 숨바꼭질 3 -bfs- 자바 (0) | 2020.12.20 |
Comments