728x90
문제풀이
두가지 접근방법
1. DFS 를 이용한 전체 탐색
- 처음에 시도했던 방법이다. 메모리 초과가 나와서 역시나했나다..
그 이유는 최대 10^5 개의 숫자를 DFS로 탐색하려면 엄청난 메모리가 사용될거라 생각했다.
이 방법이 틀린줄 알면서 풀어본 이유는 대부분의 코딩테스트는 정수론 문제는 거의 출제하지 않는것 같기 때문이다.
2. 정수론을 이용한 정렬
- 문제에서 주어지는 30 이란 숫자에서 생각해낸 방법이다.
다른분들의 풀이를 보면서 참고하였다.
1) 우선 3의 배수의 특징은 각 자리수의 합이 3의 배수라는 점이 있다.
2) 우리는 30의 배수를 찾아야 하므로 입력받은 숫자를 정렬했을때 처음에 0이 오면 된다.
3) 두 가지 조건을 이용하여 30의 배수인지 아닌지 찾았다.
소스코드1
|
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
32
33
34
35
36
37
38
39
40
41
|
import java.io.*;
import java.util.*;
public class Main {
static int n,k;
static List<Integer> list = new ArrayList<>();
static int ans = -1;
static boolean[] selected;
public static void main(String[] args) throws Exception, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringBuilder sb = new StringBuilder();
StringTokenizer st;
String num = br.readLine();
selected = new boolean[num.length()];
dfs(0, num, "");
System.out.println(ans);
}
static void dfs(int depth, String num, String source)
{
if(depth == num.length())
{
int k = Integer.parseInt(source);
if(k >= 30 && k%30 == 0)
{
ans = Math.max(ans, k);
}
return;
}
for(int i=0;i<num.length();i++)
{
if(selected[i]) continue;
selected[i] = true;
dfs(depth+1, num, source + num.charAt(i));
selected[i] = false;
}
}
}
|
cs |
소스코드2
|
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
32
33
34
|
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringBuilder sb = new StringBuilder();
StringTokenizer st;
String nums = br.readLine();
int[] num = new int[nums.length()];
int sum = 0;
for(int i=0;i<num.length;i++)
{
num[i] = nums.charAt(i) - '0';
sum += num[i];
}
Arrays.sort(num);
if(sum % 3 == 0 && num[0] == 0)
{
for(int i=0;i<num.length;i++)
{
System.out.print(num[num.length-i-1]);
}
}
else
System.out.println(-1);
}
}
|
cs |
https://www.acmicpc.net/problem/10610
10610번: 30
어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한
www.acmicpc.net
LIST
'Programming > Algorithm' 카테고리의 다른 글
| [Greedy] BOJ 1339번, 단어 수학(JAVA) (0) | 2021.11.08 |
|---|---|
| [Tree] BOJ 10610번, 트리의 지름(JAVA) (0) | 2021.11.04 |
| [Sort] BOJ 1181번, 단어 정렬(JAVA) (2) | 2021.10.31 |
| [Topology Sort] BOJ 2252번, 줄 세우기(JAVA) (0) | 2021.10.29 |
| [Kruskal MST] BOJ 1197번, 최소 스패닝 트리(JAVA) (0) | 2021.10.29 |