https://www.acmicpc.net/problem/27172
27172번: 수 나누기 게임
《보드게임컵》을 준비하다 지친 은하는 보드게임컵 참가자들을 경기장에 몰아넣고 결투를 시키는 게임 《수 나누기 게임》을 만들었습니다. 《수 나누기 게임》의 규칙은 다음과 같습니다.
www.acmicpc.net
코드설명
에라토스테네스의 체 문제입니다.
처음에 브루트포스로 모든 조합을 고려하여 진행하다가 시간초과가 났습니다.
에라토스테네스의 체는 소수를 구하는 방법의 하나입니다.
이를 응용하여, 12가 3 으로 나눠지는 것을 모든 경우를 연산하지않고 에라토스테네스의 체 거르기 로직을 활용하면 시간내에 해결 할 수 있습니다.
추가정보로 조합을 사용하지 않고, 아래와 같이 단순 반복문으로도 가능하다.
for (int i = 0; i < N; i++) {
for (int j = i + 1; j < N; j++) {
if (arr[j] % arr[i] == 0) {
answer[i] += 1;
answer[j] -= 1;
}
}
}
코드
에라토스테네스의 체를 사용한 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static int N, M;
public static int[] arr;
public static int[] selected;
public static int[] answer;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
arr = new int[N];
selected = new int[1000001];
answer = new int[N + 1];
st = new StringTokenizer(br.readLine());
for(int i=0;i<N;i++) {
arr[i] = Integer.parseInt(st.nextToken());
selected[ arr[i] ] = i + 1;
}
for(int i=0;i<N;i++) {
int start = arr[i];
for(int j= start * 2; j< 1000001; j+=start) {
if(selected[j] > 0) {
answer[ selected[j] ] -= 1;
answer[ selected[start] ] += 1;
}
}
}
for(int i=1;i<=N;i++) {
System.out.print(answer[i]+" ");
}
}
}
처음에 시간초과 나는 코드. 나누기 과정에서 만약 10000001 개의 N 의 수가 주어진다면 시간초과 가날 것이다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static int N, M;
public static int[] arr;
public static int[] selected;
public static int[] answer;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
arr = new int[N];
answer = new int[N];
st = new StringTokenizer(br.readLine());
for(int i=0;i<N;i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
selected = new int[2];
DFS( 0, 0);
for(int temp : answer) {
System.out.print(temp+" ");
}
}
public static void DFS(int level, int idx) {
if(level == 2) {
int first = selected[0];
int second = selected[1];
// System.out.println(" "+first+" "+second);
// System.out.println(" "+arr[first]+" "+arr[second]);
int firstNum = arr[first];
int secondNum = arr[second];
if(secondNum % firstNum == 0) {
answer[first] += 1;
answer[second] -= 1;
}
return ;
}
for(int i=idx; i<N;i++) {
selected[level] = i;
DFS(level + 1, i + 1);
}
}
}