문제 >> 1247. [S/W 문제해결 응용] 3일차 - 최적 경로

 

Permutation 알고리즘을 이용해 고객의 집에 대한 모든 순서를 먼저 만든다 (index 이용)

각각의 경우에 대해 거리를 계산하고, 최소값을 갱신한다.

최소값을 출력한다.

 

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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
import java.io.BufferedReader; 
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
class pair {
    int y;
    int x;
 
    public pair(int y, int x) {
        this.y = y;
        this.x = x;
    }
}
 
public class Solution1247 {
    static pair home;
    static pair company;
    static pair[] cus;
    static int ans = Integer.MAX_VALUE;
 
    public static int getDistance(pair p1, pair p2) {
        return Math.abs(p1.x - p2.x) + Math.abs(p1.y - p2.y);
    }
 
    public static void swap(int[] set, int i, int index) {
        int temp = set[i];
        set[i] = set[index];
        set[index] = temp;
    }
    
    
    static int solve(int[] set) {
        int sum=0;
        sum += getDistance(company, cus[set[0]]);
        for(int i=0;i<set.length-1;i++) {
            int idx = set[i];
            int next = set[i+1];
            sum+= getDistance(cus[idx], cus[next]);
        }
        sum+=getDistance(cus[set[set.length-1]], home);
        
        return sum;
    }
    
 
    
    public static void perm(int[] set, int size, int n, int k) {
        if (size == k) { //종료조건
            int s = solve(set);
 
            ans = ans > s? s: ans;
            return;
        }
 
        for (int i = size; i < n; i++) {
            swap(set, i, size);
            perm(set, size + 1, n, k);
            swap(set, i, size);
        }
    }
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int TC = Integer.parseInt(br.readLine());
 
        for (int tc = 1; tc <= TC; tc++) {
            int N = Integer.parseInt(br.readLine()); // 고객 수
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            int y = Integer.parseInt(st.nextToken());
            int x = Integer.parseInt(st.nextToken());
            ans = Integer.MAX_VALUE;
            int[] set = new int[N];
            company = new pair(y, x);
 
            y = Integer.parseInt(st.nextToken());
            x = Integer.parseInt(st.nextToken());
            home = new pair(y, x);
 
            cus = new pair[N];
            for (int i = 0; i < N; i++) {
                y = Integer.parseInt(st.nextToken());
                x = Integer.parseInt(st.nextToken());
                cus[i] = new pair(y, x);
            }
 
            for (int i = 0; i < N; i++) {
                set[i] = i;
            }
 
            perm(set, 0, N, N);
            
            System.out.println("#"+tc + " "+ans);
 
        }
    }
}
 
 cs
저작자표시 (새창열림)

'Algorithm Problem Solving' 카테고리의 다른 글

[SWEA] 2819 격자판의 숫자 이어 붙이기  (0) 2019.02.16
[BOJ] 9999 : 구구 **결정적 힌트**  (5) 2019.02.13
[SW Expert Academy] 1244. [S/W 문제해결 응용] 2일차 - 최대 상금  (2) 2019.02.12
[BOJ] 10819 : 차이를 최대로  (0) 2019.02.08
[BOJ] 1987 : 알파벳  (0) 2019.02.08

문제 >> 1244. [S/W 문제해결 응용] 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
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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashSet;
import java.util.StringTokenizer;
 
public class Solution_1244 {
 
        
    
    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        
        int TC = Integer.parseInt(bf.readLine()); 
        int change;
        int ans;
        
        for(int tc=1;tc<=TC;tc++) {
            StringTokenizer st = new StringTokenizer(bf.readLine()," ");
            String s = st.nextToken();
            Integer[] board = new Integer[s.length()];
            change = Integer.parseInt(st.nextToken());//교환 횟수            
                
            int[] check = new int[10];
            Arrays.fill(check, -1);
            ArrayList<Integer> al = new ArrayList<Integer>();
            for(int i=0;i<board.length;i++) { //숫자판
                board[i] = s.charAt(i)-'0';
                if(check[board[i]] != -1) { //중복된 숫자가 들어온 경우
                    //al리스트에 중복된 숫자들의 인덱스를 저장해논다.
                    if(al.isEmpty())al.add(check[board[i]]);
                    al.add(i);
                }
                else check[board[i]] = i;    
            }
            
            for(int i=0;i<board.length;i++) { //선택정렬
                if(change==0) break;
                
                int maxIndex = i;
                for(int j=i;j<board.length;j++) {
                    if(board[maxIndex]<=board[j]) {
                        maxIndex = j;
                    }
                }
                if(maxIndex != i) {
                    int tmp = board[maxIndex]; //1.가장 큰 숫자위치와 가장 왼쪽 원소 swap
                    board[maxIndex]=board[i]; 
                    board[i]=tmp;
                    change --;                    
                } 
            } //end of for 선택정렬
            
            //교환횟수가 남은 경우
            
            //동일한 숫자가 존재하면, 값의 변동없이 교환회수를 감소시킬 수 있다.
            HashSet<Integer> hs = new HashSet<Integer>(Arrays.asList(board));
            
            if(hs.size() != board.length) { // 같은 숫자 존재
                /* 처음에 저장해논 중복된 숫자들의 인덱스를 이용해 
                 * 중복 숫자들과 교환된 숫자들을 추출 후, tmpArr 배열에 저장한다.
                 * 
                 * 해당 숫자들을 sort 후 다시 입력한다.
                 * 
                 * ex ) 
                 * 3 2 1 8 8 8 , 3번 교환
                 * 알고리즘에 의하면
                 * 8 8 8 1 2 3 
                 * 이 되지만, 실제 답은
                 * 8 8 8 3 2 1 이다.
                 * 즉, 중복 숫자들과 교환된 숫자들은 다시 sort 후 대입한다. 
                 */
                Integer[] tmpArr = new Integer[al.size()];
                
                for(int i=0;i<al.size();i++) {
                    tmpArr[i] = board[al.get(i)];
                }
                
                Arrays.sort(tmpArr, new Comparator<Integer>() { //내림차순 정렬
                    @Override
                    public int compare(Integer o1, Integer o2) {
                        return o2-o1;
                    }
                });
                
                int idx = 0;
                for(int i : al) {
                    board[i] = tmpArr[idx++];
                }
            }
            
            
            
            //짝수번 남았으면 무시, 홀수 번이면 1의 자리와 10의자리를 바꿔준다.
            if(change%2 == 1 && hs.size() == board.length) {
                int len = board.length-1;
                int tmp = board[len]; //1.가장 큰 숫자위치와 가장 왼쪽 원소 swap
                board[len]=board[len-1]; 
                board[len-1]=tmp;
            } 
        
            
            
            System.out.print("#"+tc+" ");
            for(int i=0;i<board.length;i++) System.out.print(board[i]);
            System.out.println();
        }//end of tc
        
    }//end of main
}
 
 cs

 

저작자표시 (새창열림)

'Algorithm Problem Solving' 카테고리의 다른 글

[BOJ] 9999 : 구구 **결정적 힌트**  (5) 2019.02.13
[SW Expert Academy] 1247. [S/W 문제해결 응용] 3일차 - 최적 경로  (2) 2019.02.13
[BOJ] 10819 : 차이를 최대로  (0) 2019.02.08
[BOJ] 1987 : 알파벳  (0) 2019.02.08
[BOJ] 10798 : 세로읽기  (0) 2019.02.08

문제 보기 >> 5432. 쇠막대기 자르기




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
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
 
public class Solution_5432_쇠막대기자르기 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        
        for(int tc = 1 ;tc<= T ;tc++) {
            String str = br.readLine();
            char now;
            char[] arr = new char[str.length()];
            int piece = 0;
            int stick=0;
            for(int i=0;i<str.length();i++) {
                now = str.charAt(i);
                
                if(now==')') {
                    char pre = str.charAt(i-1);
                    if(pre == '(') { //레이저
                        stick--;
                        piece += stick;
                    }
                    else {
                        stick --;
                        piece++;
                    }
                }
                
                if(now == '(') {
                    stick++;
                }
                
            }
        
        
            System.out.println("#"+tc+" "+piece);
        }//testcase end
    }// end of main
}
 
cs


저작자표시 (새창열림)

'Algorithm Problem Solving' 카테고리의 다른 글

[BOJ]1389: 케빈 베이컨의 6단계 법칙  (0) 2019.02.08
[정올] 1809 : 탑  (0) 2019.01.22
1218. [S/W 문제해결 기본] 4일차 - 괄호 짝짓기  (0) 2019.01.15
[BOJ] 1018 : 체스판 다시 칠하기  (0) 2019.01.11
1206. [S/W 문제해결 기본] 1일차 - View  (0) 2019.01.11
문제 >> 1206. [S/W 문제해결 기본] 1일차 - View


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
import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Scanner;
 
public class Solution {
    public static void main(String[] args) {
        
        Scanner s = new Scanner(System.in);
        
        for(int tc=1;tc<=10;tc++) {
            int n = s.nextInt();
            int[] map = new int[n];
            
            for(int i=0;i<n;i++) {
                map[i]=s.nextInt();
            }
            
            int ans = 0;
            for(int i=2;i<map.length-2;i++) {
 
                int[] arr = new int[4];
                arr[0] = map[i-1];
                arr[1] = map[i-2];
                arr[2] = map[i+1];
                arr[3] = map[i+2];
                Arrays.sort(arr);
                if(arr[3]<map[i]) {
                    ans += (map[i]-arr[3]);
                }
            }
            System.out.println("#"+tc+" "+ans);
        }
    }
}
 
cs




빌딩의 옥상에 서있는 '나'를 기준으로 좌우로 두칸 거리에 있는 빌딩들의 높이와 비교 해본다.  




4곳 모두 (좌로 1칸, 2칸 // 우로 1칸, 2칸) 본인보다 높이가 낮다면, (현재 빌딩 높이 - 4곳중 최대높이) 가 내가 서있는 빌딩의 확보된 조망권일 것이다.



각각의 빌딩의 높이를 입력받은 배열 map 을 방문하면서


좌우로 2칸 안에 위치한 빌딩의 높이들을 arr이라는 배열에 담아주고 sort 했다. 


arr의 최대 값이 현재 빌딩의 높이보다 낮다면, (현재 빌딩의 높이 - arr의 max) 가 현재 빌딩의 조망권이다..



저작자표시 (새창열림)

'Algorithm Problem Solving' 카테고리의 다른 글

1218. [S/W 문제해결 기본] 4일차 - 괄호 짝짓기  (0) 2019.01.15
[BOJ] 1018 : 체스판 다시 칠하기  (0) 2019.01.11
1225. [S/W 문제해결 기본] 7일차 - 암호생성기  (0) 2019.01.11
[BOJ] 15686 : 치킨배달  (1) 2019.01.08
Baby-gin  (0) 2019.01.08

+ Recent posts

티스토리툴바