be programmer
27172 : 수 나누기 게임 - JAVA 본문
https://www.acmicpc.net/problem/27172
27172번: 수 나누기 게임
《보드게임컵》을 준비하다 지친 은하는 보드게임컵 참가자들을 경기장에 몰아넣고 결투를 시키는 게임 《수 나누기 게임》을 만들었습니다. 《수 나누기 게임》의 규칙은 다음과 같습니다.
www.acmicpc.net
수열이 주어지고, 두 수간 비교하여 나누어 떨어지면 나누는 수에는 1점을 가산하고, 나누어지는 수에는 1점을 감산하는 문제이다.
처음에는 단순 브루트포스로 이해하고 반복문 2개를 사용하여 모두 비교후, 나머지가 0이면 1이 나오면 각각 1점씩 가산, 감산하는 방식을 사용했으나, 시간초과가 떴다.
태그를 열어보니, 소수 판정과 에라토스테네스의 체가 있었고
승부를 봐야 하는 숫자들을 boolean에 집어넣고 그 수들만 계산하도록 했고, 밑의 두번째 반복문에서는 승부를 봐야하는 숫자의 배수만 반복하도록 반복문을 돌려서 그 배수에 승부를 봐야하는 수가 포함돼있으면 승패에 따라 점수를 감, 가산하는 작업을 수행했더니 맞았다.
맞게 나온 코드
package solution;
import java.util.*;
import java.io.*;
public class sol257 {
static int[] score;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int num = 0;
int n = Integer.parseInt(br.readLine());
int[] arr = new int[n+1];
score = new int[1000001];
boolean[] isVisible = new boolean[1000001];
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i = 1; i < n+1; i++) {
arr[i] = Integer.parseInt(st.nextToken());
isVisible[arr[i]] = true;
}
for(int i = 1; i < n+1; i++) {
num = arr[i];
//나누어 지는것 연산
for(int j = num*2; j <1000001; j+= num) {
if(isVisible[j]) {
score[num]++;
score[j]--;
}
}
}
for(int i : arr) {
if(i != 0)
sb.append(score[i] + " ");
}
System.out.println(sb.toString());
}
}
tle
package solution;
import java.util.*;
import java.io.*;
public class sol257_1 {
static boolean visit[];
static int[] score;
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[] arr = new int[n+1];
score = new int[n+1];
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i = 1; i < n+1; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
for(int i = 1; i < n+1; i++) {
for(int j = i+1; j <n+1; j++) {
vs(arr[i], arr[j], i, j);
}
}
for(int i = 1; i <= n; i++) {
bw.write(score[i] + " ");
}
bw.flush();
}
public static void vs(int a, int b, int i, int j) {
if(a % b == 0) {
score[i]--;
score[j]++;
}
if(b % a == 0) {
score[i]++;
score[j]--;
}
}
}
'알고리즘 > 문제풀이' 카테고리의 다른 글
8913 : 문자열 뽑기 - JAVA (0) | 2024.04.02 |
---|---|
13549 : 숨바꼭질 3 - JAVA (0) | 2024.04.02 |
2014 : 소수의 곱 - JAVA (0) | 2024.03.31 |
11778 : 피보나치 수와 최대공약수 - JAVA (0) | 2024.03.31 |
9251, 9252 - LCS, LCS 2 : JAVA (0) | 2024.03.29 |