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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
|
package main;
import java.util.ArrayList;
import java.util.Scanner;
public class MainClass {
final static int INF = 9999;
final static int SWITCHES = 10;
final static int CLOCKS = 16;
final static String[] str ={
"xxx.............",
"...x...x.x.x....",
"....x.....x...xx",
"x...xxxx........",
"......xxx.x.x...",
"x.x...........xx",
"...x..........xx",
"....xx.x......xx",
".xxxxx..........",
"...xxx...x...x..",
};
public static boolean areAligned(int[] arr) {
for(int b : arr) {
if(b != 12) {
return false;
}
}
return true;
}
public static void push(int[] arr, int swtch) {
int length = str[swtch].length();
for(int i = 0; i < length; ++i) {
if(str[swtch].charAt(i) == 'x') {
arr[i] += 3;
if(arr[i] == 15) {
arr[i] = 3;
}
}
}
}
public static int solve(int[] arr, int swtch) {
if(swtch == SWITCHES)
return areAligned(arr) ? 0 : INF;
int ret = INF;
for(int i = 0; i < 4; ++i) {
ret = Math.min(ret, i + solve(arr, swtch + 1));
push(arr, swtch);
}
return ret;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int test = scanner.nextInt();
ArrayList<int[]> list = new ArrayList<int[]>();
int[] arr = null;
for(int i = 0; i < test; ++i) {
arr = new int[CLOCKS];
for(int j = 0; j < CLOCKS; ++j) {
int input = scanner.nextInt();
arr[j] = input;
}
list.add(arr);
}
for(int[] a : list) {
int ret = solve(a, 0);
System.out.println(ret);
}
scanner.close();
}
}
|
cs |
위의 코드를 해석해 보면 아래와 같다.
i = 0
sw = 0
sw = 1
sw = 2
sw = 3
sw = 4
sw = 5
sw = 6
sw = 7
sw = 8
sw = 9
sw = 10
sw는 10일 때 areAlign 으로 체크하고 return false이면 12 12 12 9 9 9 12 12 12 9 12 12 12 9 12 12
0000000000 일때는 정렬이 되지 않는다는 뜻이다
그렇다면 다음 로직으로
sw 가 10 일때 i = 1이 된다.
0000000001 일때 areAlign을 체크한다.
만약
0000000000
0000000001
0000000002
0000000003
모두가 false일 경우
00000000010 부터 다시 반복문을 실시한다.
00000000010
00000000011
00000000012
00000000013
위와 같은 행동을 반복해서 ret의 최소값을 알아낸다.
10중 반복문과 같은 일을 한다.
i를 계산하는 예를 들어 보면
0000000012 에서 areAlign = true; 라고 하면
for문의 i 는
sw 버튼을 i 번만큼 눌렀다는 뜻이고 INF값과 비교하여 작은 수가 return 되기 때문에
sw10번 버튼의 눌린 횟수를 return 해준다.
그 다음 reutrn한 i값과 sw가 9 일때 눌러준 i 값을 더해주면
총 버튼을 누른 값이 나온다.
재귀함수를 마지막 까지 반복하다 보면 ret값은 가장 최소값이 return 된다.
'알고리즘 > 알고리즘 문제해결전략' 카테고리의 다른 글
예제 : 수열의 빠른 합 (0) | 2020.11.23 |
---|---|
예제 : 여행하는 외판원 (0) | 2020.11.09 |
문제 ID : BOARDCOVER , 난이도: 하 (0) | 2020.11.04 |
문제 ID : PICNIC, 난이도: 하 (0) | 2020.11.02 |