이번 문제처럼 여러번 소수를 사용하는 문제에서도 필요한 범위의 소수를 미리 구해놓고 정답체크를 진행하면 매번 새로 소수를 구하는 것보다 좋은 성능을 얻을 수 있습니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class q4698Re_SWEA_테네스의특별한소수 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int T = Integer.parseInt(br.readLine());
StringBuilder sb = new StringBuilder();
int[] arr = new int[1_000_001];
arr[1] = 1;
for (int i = 2; i <= 1_000_000; i++) {
if (arr[i] == 0) {
for (int j = i * 2; j <= 1_000_000; j += i) {
arr[j] = 1;
}
}
}
for (int t = 1; t <= T; t++) {
st = new StringTokenizer(br.readLine());
int D = Integer.parseInt(st.nextToken());
int A = Integer.parseInt(st.nextToken());
int B = Integer.parseInt(st.nextToken());
int cnt = 0;
for (int i = A; i <= B; i++) {
if (arr[i] == 0) {
if (String.valueOf(i).contains(String.valueOf(D))) {
cnt++;
}
}
}
sb.append("#").append(t).append(" ").append(cnt).append("\n");
}
System.out.println(sb);
}
}
import java.util.Scanner;
class q11285_SWEA_다트게임 {
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int T, TC, sum;
long x, y;
T = sc.nextInt();
for (int testcase = 1; testcase < T + 1; testcase++) {
TC = sc.nextInt();
sum = 0;
for (int i = 0; i < TC; i++) {
x = sc.nextInt();
y = sc.nextInt();
if (40000 < x * x + y * y)
sum += 0;
else if (32400 < x * x + y * y)
sum += 1;
else if (25600 < x * x + y * y)
sum += 2;
else if (19600 < x * x + y * y)
sum += 3;
else if (14400 < x * x + y * y)
sum += 4;
else if (10000 < x * x + y * y)
sum += 5;
else if (6400 < x * x + y * y)
sum += 6;
else if (3600 < x * x + y * y)
sum += 7;
else if (1600 < x * x + y * y)
sum += 8;
else if (400 < x * x + y * y)
sum += 9;
else
sum += 10;
}
System.out.println("#" + testcase + " " + sum);
}
}
}
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class q11285_SWEA_다트게임Re {
static StringTokenizer st;
static StringBuilder sb = new StringBuilder();
public static void main(String args[]) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T, TC, sum, x, y;
T = Integer.parseInt(br.readLine());
for (int t = 1; t < T + 1; t++) {
TC = Integer.parseInt(br.readLine());
sum = 0;
for (int tc = 0; tc < TC; tc++) {
st = new StringTokenizer(br.readLine());
x = Integer.parseInt(st.nextToken());
y = Integer.parseInt(st.nextToken());
int far = (x * x) + (y * y);
if (40000 < far)
sum += 0;
else if (32400 < far)
sum += 1;
else if (25600 < far)
sum += 2;
else if (19600 < far)
sum += 3;
else if (14400 < far)
sum += 4;
else if (10000 < far)
sum += 5;
else if (6400 < far)
sum += 6;
else if (3600 < far)
sum += 7;
else if (1600 < far)
sum += 8;
else if (400 < far)
sum += 9;
else
sum += 10;
}
sb.append("#").append(t).append(" ").append(sum).append("\n");
}
System.out.println(sb);
}
}
3. 원과 사각형간에 포함관계가 없음 (일부만 겹치거나 아예 겹치지 않음) = 두가지 색이 모두 보임
입력에 따라 조건만 잘 나누어주시면 해결됩니다.
제 풀이에서는 사각형의 네개의 꼭짓점 (a,b) (a,d) (c,b) (c,d)이 하나라도 원 밖에 있는지를 체크하고 (모두 안쪽인 경우 1번 케이스에 해당), 다음 조건문으로 사각형의 모든 꼭짓점이 원 밖에 있는지를 체크(2번 케이스) 아니라면 3번 케이스가 됩니다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
class q11112_SWEA_셀로판지 {
public static void main(String args[]) throws Exception {
int T, a, b, c, d, p, q, r;
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
T = Integer.parseInt(br.readLine());
for (int test_case = 1; test_case < T + 1; test_case++) {
st = new StringTokenizer(br.readLine());
p = Integer.parseInt(st.nextToken());
q = Integer.parseInt(st.nextToken());
r = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
a = Integer.parseInt(st.nextToken());
b = Integer.parseInt(st.nextToken());
c = Integer.parseInt(st.nextToken());
d = Integer.parseInt(st.nextToken());
if ((p - a) * (p - a) + (q - b) * (q - b) > r * r
|| (p - a) * (p - a) + (q - d) * (q - d) > r * r
|| (p - c) * (p - c) + (q - b) * (q - b) > r * r
|| (p - c) * (p - c) + (q - d) * (q - d) > r * r) {
if (p + r > c || p - r < a || q + r > d || q - r < b) {
System.out.println("#" + test_case + " YY");
} else {
System.out.println("#" + test_case + " NY");
}
} else {
System.out.println("#" + test_case + " YN");
}
}
br.close();
}
}
간단한 BFS응용 문제입니다. 모든 땅들을 기준으로 물까지의 거리를 생각하면 재귀나 백트래킹으로 계산해야겠지만, 물을 시작점으로 놓고 BFS를 돌리면 땅과의 거리를 쉽게 알 수 있습니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class q10966_SWEA_물놀이를가자 {
static StringTokenizer st;
static StringBuilder sb = new StringBuilder();
static int[][] delta = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
static int N, M;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
int answer;
for (int tc = 1; tc <= T; tc++) {
answer = 0;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
boolean[][] visit = new boolean[N][M];
Queue<int[]> queue = new LinkedList<>();
for (int n = 0; n < N; n++) {
String str = br.readLine();
for (int m = 0; m < M; m++) {
if (str.charAt(m) == 'W') {
visit[n][m] = true;
queue.add(new int[] { n, m, 0 });
}
}
}
while (!queue.isEmpty()) {
int[] now = queue.poll();
int x = now[0];
int y = now[1];
int l = now[2];
answer += l;
for (int i = 0; i < 4; i++) {
int nX = x + delta[i][0];
int nY = y + delta[i][1];
if(isIn(nX,nY) && !visit[nX][nY]) {
visit[nX][nY] = true;
queue.offer(new int[] {nX,nY,l+1});
}
}
}
sb.append("#").append(tc).append(" ").append(answer).append("\n");
}
System.out.println(sb);
}
static boolean isIn(int x, int y) {
if (0 <= x && x < N && 0 <= y && y < M) {
return true;
}
return false;
}
}