문제 >> [BOJ] 9663 : N-Queen


Backtracking을 이용하는 대표적인 문제입니다 -!

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
import java.io.BufferedReader;
import java.io.InputStreamReader;
 
//BOJ :: 9663 N-Queen
//2019-03-05
public class Main9663_NQueen {
    static int[][] map;
    static int n, ans;
 
    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
 
        n = Integer.parseInt(bf.readLine());
        ans = 0;
 
        // 1행에서 퀸의 위치를 정해준다.
        for (int j = 0; j < n; j++) {
            map = new int[n][n];
            solve(0, j, 1);
        }
        System.out.println(ans);
    }
 
    static int[] dx = { -1, 0, 1, 0, 1, -1, 1, -1 };
    static int[] dy = { 0, 1, 0, -1, -1, -1, 1, 1 };
 
    public static void solve(int y, int x, int q) {
 
        map[y][x]++; // visited
        
        //(y,x) 좌표에 퀸을 놓고 다른 퀸을 놓을수 없는 곳에 visit check 를 한다.
        //퀸의 위치를 중심으로 8방향에 대하여 배열의  범위를 초과하는 지점까지 while문을 반복한다.
        for (int i = 0; i < 8; i++) {
            int ny = y, nx = x;
            while (true) {
                ny += dy[i];
                nx += dx[i];
 
                if (ny < 0 || ny > n - 1 || nx < 0 || nx > n - 1)
                    break;
                map[ny][nx]++;
            }
        }
 
        if (q == n) {// 종료조건 : n개의 퀸을 놓으면 재귀함수를 종료한다.
            ans++;
            return;
        }
        
        //다음행인 (y+1)행에 퀸을 놓을 수 있는 곳을 탐색한다.
        for (int k = 0; k < n; k++) {
            if (map[y + 1][k] > 0)
                continue; // 방문한 곳은 continue;
 
            solve(y + 1, k, q + 1);
            
            
            //Backtracking
            //놓았던 퀸을 회수하고,
            map[y + 1][k]--;
            //해당 퀸에 의해 visit 체크 되었던 곳을 해제한다.
            for (int i = 0; i < 8; i++) {
                int ny = y + 1, nx = k;
                while (true) {
                    ny += dy[i];
                    nx += dx[i];
 
                    if (ny < 0 || ny > n - 1 || nx < 0 || nx > n - 1)
                        break;
                    map[ny][nx]--;
                }
            }
 
        }
 
    }
}
 
cs


**** visit 체크를 boolean 타입이 아닌 cnt++ 로 해주는 이유


여러 퀸을 놓으면서 해당 퀸에 의해서 8방향으로 visit 체크 되는곳이 겹치는 경우가 발생합니다.


만약, 재귀 함수가 끝나고 퀸을 회수하면서 visit 체크를 해제할때 boolean 타입으로 true를 false로 바꿔준다면


다른 퀸에 대해 visit 체크 되었던 곳임에도 불구하고 visit이 해제 될 수 있습니다.


int 형으로 카운트 해주며 visit을 체크하면 그런 상황을 방지할 수 있읍니당 ,,

저작자표시

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

[SWEA] 5656 : [모의 SW 역량테스트] 벽돌 깨기  (1) 2019.03.07
[SWEA] 1258 : [S/W 문제해결 응용] 7일차 - 행렬찾기  (0) 2019.03.07
[SWEA] 7236 : 저수지의 물의 총 깊이 구하기  (1) 2019.03.07
[SWEA] 1861 : 정사각형 방  (0) 2019.03.07
[BOJ] 8983 : 사냥꾼 / [JUNGOL] 2364 : 사냥꾼  (1) 2019.03.07

문제 >> [SWEA] 7236 : 저수지의 물의 총 깊이 구하기

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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Queue;
import java.util.StringTokenizer;
 
//SWEA :: 7236 저수지의 물의 총 깊이 구하기
//2019-03-07
public class Solution_7236_저수지의물의총깊이구하기_유승아 {
    static char[][] map;
    static int[][] count;
    static int n;
 
    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
 
        int T = Integer.parseInt(bf.readLine());
 
        for (int tc = 1; tc <= T; tc++) {
 
            n = Integer.parseInt(bf.readLine());
            map = new char[n][n];
            count = new int[n][n];
            for (int i = 0; i < n; i++) {
                StringTokenizer st = new StringTokenizer(bf.readLine(), " ");
                for (int j = 0; j < n; j++) {
                    map[i][j] = st.nextToken().charAt(0);
                }
            } // input
            int ans = Integer.MIN_VALUE;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (map[i][j] == 'G')
                        continue;
                    solve(i, j);
                    ans = ans < count[i][j] ? count[i][j] : ans;
                }
            }
            System.out.println("#" + tc + " " + ans);
 
        } // end of tc
    }// end of main
 
    static int[] dx = { -1, 1, 0, 0, 1, 1, -1, -1 };
    static int[] dy = { 0, 0, -1, 1, -1, 1, -1, 1 };
 
    public static void solve(int y, int x) {
 
        int wCnt = 0;
        for (int i = 0; i < 8; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];
 
            if (ny < 0 || ny > n - 1 || nx < 0 || nx > n - 1)
                continue;
 
            if (map[ny][nx] == 'W')
                wCnt++;
 
        }
 
        if (wCnt == 0)
            count[y][x] = 1;
        else
            count[y][x] = wCnt;
 
    }
 
}
 
cs


저작자표시

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

[SWEA] 1258 : [S/W 문제해결 응용] 7일차 - 행렬찾기  (0) 2019.03.07
[BOJ] 9663 : N-Queen  (0) 2019.03.07
[SWEA] 1861 : 정사각형 방  (0) 2019.03.07
[BOJ] 8983 : 사냥꾼 / [JUNGOL] 2364 : 사냥꾼  (1) 2019.03.07
[BOJ] 1012 : 유기농배추  (1) 2019.02.17
문제 >> [SWEA] 1861 : 정사각형 방


dp로 풀었음.

완탐도 가능 !



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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
//SWEA :: 1861 정사각형 방
//2019-03-07
public class Solution1861_정사각형방_유승아 {
    static int[][] box;
    static int[][] dp;
    static int n;
 
    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
 
        int T = Integer.parseInt(bf.readLine());
 
        for (int tc = 1; tc <= T; tc++) {
 
            n = Integer.parseInt(bf.readLine());
            box = new int[n][n];
            dp = new int[n][n]; //방문한 방의 갯수를 저장할 배열
 
            for (int i = 0; i < n; i++) {
                StringTokenizer st = new StringTokenizer(bf.readLine(), " ");
                for (int j = 0; j < n; j++) {
                    box[i][j] = Integer.parseInt(st.nextToken());
                }
            } // input
 
            int max = Integer.MIN_VALUE;
            int start = Integer.MAX_VALUE;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    //dp배열의 값이 0일 때만 방문
                    //0이 아닌 경우는 이미 해당 방에서 갈 수 있는 최대값이 저장되어 있다.
                    if (dp[i][j] == 0) {
                        solve(i, j);
                    }
                    
                    //최대값 갱신
                    if (max < dp[i][j]) {
                        max = dp[i][j];
                        start = box[i][j];
                    } else if (max == dp[i][j]) {
                        //최대값이 같은 경우에는 start 숫자가 작은 값을 저장한다.
                        start = start > box[i][j] ? box[i][j] : start;
                    }
 
                }
            }
 
            System.out.println("#" + tc + " " + start + " " + max);
        } // end of tc
 
    }// end of main
 
    static int[] dx = { -1, 1, 0, 0 };
    static int[] dy = { 0, 0, -1, 1 };
 
    public static void solve(int y, int x) {
        dp[y][x] = 1;
 
        for (int i = 0; i < 4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];
 
            if (ny < 0 || ny > n - 1 || nx < 0 || nx > n - 1 )
                continue;
 
            if (box[ny][nx] == box[y][x] + 1) {
                //아직 방문한 적이 없을때만 solve 함수를 호출한다.
                if( dp[ny][nx] == 0) solve(ny, nx);
                
                //최대값으로 갱신한다.
                if (dp[y][x] < 1 + dp[ny][nx]) {
                    dp[y][x] = 1 + dp[ny][nx];
                }
            }
        }
    } // end of solve
 
}
 
cs


저작자표시

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

[BOJ] 9663 : N-Queen  (0) 2019.03.07
[SWEA] 7236 : 저수지의 물의 총 깊이 구하기  (1) 2019.03.07
[BOJ] 8983 : 사냥꾼 / [JUNGOL] 2364 : 사냥꾼  (1) 2019.03.07
[BOJ] 1012 : 유기농배추  (1) 2019.02.17
[BOJ] 1931 : 회의실배정 (++그리디 알고리즘에 대한 고찰)  (2) 2019.02.17
문제 >> 백준 8389 사냥꾼   /   정올 2635 사냥꾼









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
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
//정올 2364 사냥꾼
//백준 8983 사냥
//2019-03-05
 
public class Main_8983{
    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine(), " ");
        int M = Integer.parseInt(st.nextToken()); // 사대 수
        int N = Integer.parseInt(st.nextToken()); // 동물 수
        long L = Integer.parseInt(st.nextToken()); // 사정거리
        int ans = 0;
        long yy = Long.MIN_VALUE;
        long xx = Long.MIN_VALUE;
        long[] gun = new long[M+1];
        pair[] animal = new pair[N];
        st = new StringTokenizer(bf.readLine(), " ");
        for (int i = 0; i < M; i++) {
            int token = Integer.parseInt(st.nextToken());
 
            gun[i] = token;
        }
        gun[M] = 1000000001;
        Arrays.sort(gun);
 
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(bf.readLine(), " ");
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
             
 
            animal[i] = new pair(x, y);
        }
        Arrays.sort(animal);
 
        /*
         * gun과 animal의 좌표를 x를 기준으로 정렬한다. 
         * animal을 기준으로 두고, gun을 순회한다. 
         * gun의 처음부터 순회하다가 사정거리 안에 포함되는 사대를 발견했을 때, 카운트 해주고 사대의 시작 위치를 바꿔준다. 
         * 다음 동물은 현재 사대부터 보면 된다 .
         */
 
        int cur = 0;
        for (int i = 0; i < N; i++) {
            pair p = animal[i];
            int ax = p.x;
            int ay = p.y;
            if (ay > L || ax < gun[0] - L ) continue;
            
            //animal의 x좌표가 gun의 최대  최대 범위보다 커지는 경우 그 이후의 좌표는 탐색하지 않아도 된다.
            if (ax > gun[M - 1] + L) break;
 
            for (int j = cur; j < M; j++) { // 사대 검사
                long dist = getDist(gun[j],ax,ay);
                if(dist<=L) {
                    ans++;
                    cur = j;
                    break;
                }
                //사정거리안에 없으면서 gun의 x값이 크면 break
                if(ax<gun[j]) break;
 
            }
 
        }
 
        System.out.println(ans);
    }
 
    public static long getDist(long x, int a, int b) {
        return Math.abs(x - a) + b;
    }
 
    static class pair implements Comparable<pair> {
        int x;
        int y;
 
        public pair(int x, int y) {
            super();
            this.x = x;
            this.y = y;
        }
 
        @Override
        public int compareTo(pair o) {
            // TODO Auto-generated method stub
            return this.x-o.x;//오름차순 
        }
    }
}
 
cs


저작자표시

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

[SWEA] 7236 : 저수지의 물의 총 깊이 구하기  (1) 2019.03.07
[SWEA] 1861 : 정사각형 방  (0) 2019.03.07
[BOJ] 1012 : 유기농배추  (1) 2019.02.17
[BOJ] 1931 : 회의실배정 (++그리디 알고리즘에 대한 고찰)  (2) 2019.02.17
[SWEA] 2819 격자판의 숫자 이어 붙이기  (0) 2019.02.16

문제 >> 1012 : 유기농배추



dfs를 이용


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
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main_1012 {
//유기농 배추
    
    static int[][] map;
    static int[] dy = {0,0,-1,1};
    static int[] dx = {-1,1,0,0};
    static int M,N;
    
    
    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        
        int T = Integer.parseInt(bf.readLine());
        
        for(int tc=1;tc<=T;tc++) {
            
            StringTokenizer st = new StringTokenizer(bf.readLine()," ");
            M = Integer.parseInt(st.nextToken()); //가로
            N = Integer.parseInt(st.nextToken()); //세로
            int K = Integer.parseInt(st.nextToken()); //배추개수
            
            map = new int[N][M];
            
            
            
            for(int i=0;i<K;i++) {
                st = new StringTokenizer(bf.readLine()," ");
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());
                map[y][x]=1;
            }
            
            int ans=0;
            for(int i=0;i<N;i++) {
                for(int j=0;j<M;j++) {
                    if(map[i][j] == 1) {
                        dfs(i,j);
                        ans++;
                    }
                }
            }
            System.out.println(ans);
        }//end of tc
    }
 
 
    static void dfs(int y, int x) {
        map[y][x]=0; //visited check
        
        for(int i=0;i<4;i++) {
            int ny = y+dy[i];
            int nx = x+dx[i];
            
            if(ny<0 || ny>N-1 || nx<0 || nx>M-1) continue;
            if(map[ny][nx] == 1) dfs(ny,nx);
        }
        
        return ;
    }
}
 
cs


저작자표시

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

[SWEA] 1861 : 정사각형 방  (0) 2019.03.07
[BOJ] 8983 : 사냥꾼 / [JUNGOL] 2364 : 사냥꾼  (1) 2019.03.07
[BOJ] 1931 : 회의실배정 (++그리디 알고리즘에 대한 고찰)  (2) 2019.02.17
[SWEA] 2819 격자판의 숫자 이어 붙이기  (0) 2019.02.16
[BOJ] 9999 : 구구 **결정적 힌트**  (5) 2019.02.13

* Greedy 알고리즘 (탐욕적 알고리즘)


완전탐색 , 동적 계획법 --> 모든 선택지를 고려해 보고 그중 전체 답이 가장 좋은 것을 찾는다.


그리디 알고리즘 --> 각 단계마다 지금 당장 가장 좋은 방법만을 선택한다. 

     즉, 지금의 선택이 앞으로 남은 선택들에 어떤 영향을 끼칠지는 고려하지 않는다.


따라서 알고리즘의 정당성을 증명하는 과정이 필수적이다.!



문제보기 >> 백준 1931 : 회의실배정 


가장 먼저 끝나는 회의를 선택하고, 이 회의와 겹치지 않는 회의중 가장 먼저 끝나는 회의를 선택하는 것을 반복한다.


((정당성의 증명))

" 가장 종료 시간이 빠른 회의를 포함하는 최적해가 반드시 존재한다." 를 증명해보자.


S는 회의 목록, Smin 은 가장 일찍 끝나는 회의.


S의 최적해 중 Smin을 포함하지 않는 답이 있다고 가정하자

이 답은 서로 겹치지 않는 회의의 목록이다.

이 목록에서 첫번째로 개최되는 회의를 지우고 Smin 을 추가해 새로운 목록을 만든다.

Smin은 S에서 가장 일찍 끝나는 회의의기 때문에, 지워진 회의는 Smin보다 일찍 끝날수 없다.

따라서 두번쨰 회의와 Smin이 겹치는 일은 없으며, 새로 만든 목록도 최적해가 될 수 있다.


==> 항상 Smin을 포함하는 최적해는 존재한다.

==> 가장 일찍 끝나는 회의를 선택해서 최적해를 얻는 것이 불가능해지는 경우는 없다.



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
import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;
 
public class Main_1931 {
    //회의실배정
    static int N;
    static int[][] arr;
 
    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        
        N = Integer.parseInt(bf.readLine());
        arr=new int[N][2];
        for(int i=0;i<N;i++) {
            StringTokenizer st = new StringTokenizer(bf.readLine()," ");
            arr[i][0] = Integer.parseInt(st.nextToken());
            arr[i][1] = Integer.parseInt(st.nextToken());
        }
        
        Arrays.sort(arr,new Comparator<int[]>() {
            //0 : o1==o2
            //1 : o1>o2
            //-1 : o1<o2
            //arr[n][1]을 기준으로 오름차순 정렬
            @Override
            public int compare(int[] o1, int[] o2) {
                if(o2[1]==o1[1]) {
                    return o1[0]-o2[0];
                }
                else return o1[1]-o2[1];
        
            
            }
        });
    
    
        
 
        System.out.println(solve());
        
    
    }
    
    static int solve(){
        
        int now=0;
        int cnt=1;
        
        for(int i=1;i<N;i++) {
            //다음 회의의 시작시간이 현재 회의의 종료시간보다 작으면 continue
            if(arr[i][0]<arr[now][1]) continue;
        
            cnt++;
            now=i;
        }
        
        
        return cnt;
 
        
    }//end of solve
 
}
 
cs



++) 고민해야할 예외 상황



2

2 2

1 2


와같은 입력이 있다면,


(1 2) -> (2 2) 


의 순서로 회의실 배정을 할 수 있고 답은 2일것이다.


하지만 회의 종료시간만을 기준으로 data를 정렬하면


(2 2) 가 우선 순위가 되어 (1 2) 배정은 불가능하다고 판단할수도 있다.


따라서 정렬 과정에서,


회의 종료시간이 같다면, 회의 시작시간을 기준으로 한 오름차순 정렬을 해줘야한다.

저작자표시

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

[BOJ] 8983 : 사냥꾼 / [JUNGOL] 2364 : 사냥꾼  (1) 2019.03.07
[BOJ] 1012 : 유기농배추  (1) 2019.02.17
[SWEA] 2819 격자판의 숫자 이어 붙이기  (0) 2019.02.16
[BOJ] 9999 : 구구 **결정적 힌트**  (5) 2019.02.13
[SW Expert Academy] 1247. [S/W 문제해결 응용] 3일차 - 최적 경로  (2) 2019.02.13

문제 >> 2819. 격자판의 숫자 이어 붙이기 

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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.StringTokenizer;
 
public class Main_2819 {
    static HashSet<String> hs;
    static int[] dy = { -1, 1, 0, 0 };
    static int[] dx = { 0, 0, -1, 1 };
    static char[][] map = new char[4][4];
 
    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
 
        int T = Integer.parseInt(bf.readLine());
 
        for (int tc = 1; tc <= T; tc++) {
            hs = new HashSet<String>();
            for (int i = 0; i < 4; i++) {
                StringTokenizer st = new StringTokenizer(bf.readLine(), " ");
                for (int j = 0; j < 4; j++) {
                    map[i][j] = st.nextToken().charAt(0);
                }
            } // 입력 받기
 
            for (int i = 0; i < 4; i++) {
                for (int j = 0; j < 4; j++) {
                    solve(i, j, 0, "" + map[i][j]);
                }
            }
 
            System.out.println("#" + tc + " " + hs.size());
        } // end of tc
    }
 
    static void solve(int y, int x, int depth, String s) {
 
        if (depth >= 6) {
            hs.add(s);
            return;
        } else {
            for (int i = 0; i < 4; i++) {
                int ny = y + dy[i];
                int nx = x + dx[i];
 
                if (ny < 0 || ny > 3 || nx < 0 || nx > 3)
                    continue;
 
                s = map[ny][nx]+s;
                
                solve(ny, nx, depth+1, s);
                
                s=s.substring(1);
        
            }
        }
 
    } // end of solve
}
 
cs


중복체크를 위해 Hashset을 사용했다.

Hashset은 중복된 원소에 대한 체크를 자동으로 해주기때문에

모든 경우를 Hashset에 삽입하고, 마지막에 Hashset의 size를 출력해주었다.


보통 중복체크는 boolean 타입의 배열을 사용하지만

문제에서  "0으로 시작하는 0102001과 같은 수를 만들 수도 있다." 라는 부분때문에

인덱스로 사용하지 못할 것으로 판단했다.


하지만 일곱자리 수로 결정되어있으므로 0으로 시작하는 숫자도 Integer 형으로 변환시키면

자동으로 앞의 0이 제거되면서 중복되지 않는 index가 될 수 있다.

0000123 => 123

0010234 => 10234

이런식으로 활용이 가능하다 

중복이 되지 않는 이유는 7자리로 고정되어있기때문이고

자리수가 고정되어있지않으면 활용이 불가능하다

 !


저작자표시

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

[BOJ] 1012 : 유기농배추  (1) 2019.02.17
[BOJ] 1931 : 회의실배정 (++그리디 알고리즘에 대한 고찰)  (2) 2019.02.17
[BOJ] 9999 : 구구 **결정적 힌트**  (5) 2019.02.13
[SW Expert Academy] 1247. [S/W 문제해결 응용] 3일차 - 최적 경로  (2) 2019.02.13
[SW Expert Academy] 1244. [S/W 문제해결 응용] 2일차 - 최대 상금  (2) 2019.02.12

백준 7대 난제 중 한 문제인 구구


문제 >> 9999 : 구구


<<HINT>>


1. 여자 가수다.

2. 가사는 영어가 아니다.

3. 앨범과 노래 제목이 동일하다


---------------------

이미 공개된 힌트

1. ep --> 가수 이름의 이니셜

2. 제목이 12byte

3. e로 끝난다

4. 1915년 출생, 1950년 발매된 앨범의 수록곡


저작자표시

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

[BOJ] 1931 : 회의실배정 (++그리디 알고리즘에 대한 고찰)  (2) 2019.02.17
[SWEA] 2819 격자판의 숫자 이어 붙이기  (0) 2019.02.16
[SW Expert Academy] 1247. [S/W 문제해결 응용] 3일차 - 최적 경로  (2) 2019.02.13
[SW Expert Academy] 1244. [S/W 문제해결 응용] 2일차 - 최대 상금  (2) 2019.02.12
[BOJ] 10819 : 차이를 최대로  (0) 2019.02.08

+ Recent posts

티스토리툴바