문제링크 : https://www.acmicpc.net/problem/2004

 

2004번: 조합 0의 개수

첫째 줄에 정수 n, m(0≤m≤n≤2,000,000,000, n!=0)이 들어온다.

www.acmicpc.net

이 문제를 풀기 위해서는, 일단 고등학교 때 수학 시간에 배웠던 조합에 대한 기억을 되살려야한다. 많은 걸 기억해낼 필요는 없고, 밑에 있는 공식 하나만 기억하면 된다.

조합의 값 끝자리 0의 개수를 구하기 위해서는, 조합의 값을 소인수분해 했을 때 10 (2 X 5)을 얼마나 많이 가지고 있는지를 구하면 된다. 예를 들면, 50은 5 X 10이니까 0이 한 개이다. 342000은 342 X 10 X 10 X 10이니까 0이 세 개이다.

 

당연히 조합값을 다 구한 다음에 계산하는 것은 불가능에 가깝다. n, m의 최대값이 int의 최대값에 가까운 상황에서 팩토리얼 계산이 들어가버리면... 아무리 큰 자료형을 쓴다고 해도 그것들을 다 담아내는 것은 거의 불가능할 것이다. 어차피 우리가 궁금한 것은 조합값 자체가 아니라 조합값을 소인수분해했을 때 포함되어있는 2와 5의 개수이다.

 

팩토리얼 계산에 들어가는 값들을 일일히 소인수분해하여 2와 5의 개수를 셀 수도 있을 것이다. 필자는 처음에 그렇게 생각하고 풀었으나... 시간초과가 떴다...ㅠㅠ 시간초과로 실패한 필자의 코드는 아래와 같다.

 

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
 
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        
        long twoCnt = 0;
        long fiveCnt = 0;
        
        twoCnt = getCnt(n, 2) - getCnt(m, 2) - getCnt(n - m, 2);
        fiveCnt = getCnt(n, 5) - getCnt(m, 5) - getCnt(n - m, 5);
        
        System.out.println(Math.min(twoCnt, fiveCnt));
    }
 
    private static long getCnt(int n, int a) {
        long cnt = 0;
        
        for(int i = a; i <= n; i += a) {
            int temp = i;
            
            while(temp != 0 && temp % a == 0) {
                cnt++;
                temp /= a;
            }
        }
        
        return cnt;
    }
}
  

 

시간초과가 뜨자 위의 코드를 여러 방식으로 바꾸어 보았다. 한 번의 연산에서 2와 5를 모두 계산하고, 조합 자체의 수학 공식을 변형하여 더 적은 연산횟수로 바꿔보기도 했으나, 일일히 소인수분해를 해서 개수를 확인한다는 컨셉 내에서는 결국 시간초과를 벗어날 수 없었다. 결국 구글링 ㄱㄱ...ㅠㅠ

 

이제 구글링을 통해 풀어낸 풀이에 대한 설명을 하겠다. 소인수분해를 통해 2와 5의 개수를 구한다는 기본컨셉은 동일하다. 근데 그 개수를 구하는 방식에 차이가 있다.

 

59!을 소인수 분해했을 때 5가 몇 개 있는지를 구하는 과정을 예를 들어 설명해보겠다.

59! = 59 X 58 X 57 X 56 X ..... X 2 X 1

즉, 1 ~ 59 수의 곱이다. 그렇다면 이 중 5의 배수는 몇 개일까? 59 / 5 = 11개이다. 11개 이 외의 수들은 체크해볼 필요도 없이 5를 소인수로 포함하고 있지 않을 것이다. 11개의 수를 나열해보면, 55 X 50 X 45 ... 10 X 5 이다. 59!은 최소한 11개의 5를 소인수로 가지고 있는 것이다. 11개의 5는 이제 카운트 되었으니, 각각의 11개의 수들을 5로 나눠보면,

11 X 10 X 9 X ... X 2 X 1 이 된다. 여기에서 5의 배수의 개수는 11 /5 = 2개가 된다. 이런 방식을 통해, 59!을 소인수분해했을 때 5는 총 13개가 있다는 것을 알 수 있다. 코드는 아래와 같다.

 

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
 
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());        
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        
        int twoCnt = get(n, 2) - get(m, 2) - get(n - m, 2);
        int fiveCnt = get(n, 5) - get(m, 5) - get(n - m, 5);
        
        System.out.println(Math.min(twoCnt, fiveCnt));
    }
    
    private static int get(int n, int k) {
        int cnt = 0;
        
        while(n >= k) {
            cnt += n / k;
            n /= k;
        }
        
        return cnt;
    }
}
 
  

 

위와 같은 방식으로 소인수의 개수를 구할 수 있다는 아이디어를 떠올리는 것이 어렵다... 유레카!하고 떠오르면 좋겠다만 천재가 아닌 이상 그게 쉽진 않을 것 같다. 결국 이런 풀이의 경우 외우고 있는 것이 좋을 것 같다는 생각이 든다.

 

저작자표시

'알고리즘' 카테고리의 다른 글

백준(BOJ) 11662 : 민호와 강호 (JAVA)  (0) 2020.02.07
백준(BOJ) 10816 : 숫자 카드 2 (JAVA)  (2) 2020.02.04
백준(BOJ) 1697 : 숨바꼭질 (JAVA)  (0) 2020.02.03
백준(BOJ) 2225 : 합분해 (JAVA)  (0) 2020.02.02
백준(BOJ) 1654 : 랜선 자르기 (JAVA)  (0) 2020.01.31

문제링크 : https://www.acmicpc.net/problem/1697

 

1697번: 숨바꼭질

문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지

www.acmicpc.net

전형적인 BFS문제이다. 주의할 점은,

1. 좌표값이 0 일 때는 X-1, X*2를 해선 안된다.

2. 좌표값이 K(동생의 위치) 보다 클 때는 X+1, X*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
 
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        
        if(n >= k) {
            System.out.println(n - k);
        } else {
            boolean[] visited = new boolean[k * 2 + 1];
            visited[n] = true;
            Queue<Status> queue = new LinkedList<Status>();
            queue.offer(new Status(n, 0));
            
            int answer = 0;
            
            outer : while(!queue.isEmpty()) {
                Status poll = queue.poll();
                int position = poll.getPosition();
                int time = poll.getTime();
                    
                for(int i = 0; i < 3; i++) {
                    int nextPosition = getNextPosition(position, k, i);
                    
                    if(nextPosition != -1 && !visited[nextPosition]) {
                        
                        if(nextPosition == k) {
                            answer = time + 1;
                            break outer;
                        }
                        
                        visited[nextPosition] = true;
                        queue.offer(new Status(nextPosition, time + 1));
                    }
                }
            }
            
            System.out.println(answer);
        }
    }
    
    private static int getNextPosition(int position, int k, int idx) {
        int nextPosition = -1;
        
        switch (idx) {
        case 0:
            if(position > 0) {
                nextPosition = position - 1;
            }
            break;
        case 1:
            if(position > 0 && position < k) {
                nextPosition = position * 2;
            }
            break;
        default:
            if(position < k) {
                nextPosition = position + 1;
            }
            break;
        }
        
        return nextPosition;
    }
    
    private static class Status {
        private int position;
        private int time;
        
        public Status(int position, int time) {
            this.position = position;
            this.time = time;
        }
        
        public int getPosition() {
            return position;
        }
        public int getTime() {
            return time;
        }
    }
}
 
  

 

 

저작자표시

'알고리즘' 카테고리의 다른 글

백준(BOJ) 10816 : 숫자 카드 2 (JAVA)  (2) 2020.02.04
백준(BOJ) 2004 : 조합 0의 개수 (JAVA)  (0) 2020.02.04
백준(BOJ) 2225 : 합분해 (JAVA)  (0) 2020.02.02
백준(BOJ) 1654 : 랜선 자르기 (JAVA)  (0) 2020.01.31
백준(BOJ) 1931 : 회의실배정 (JAVA)  (0) 2020.01.30

문제링크 : https://www.acmicpc.net/problem/2225

 

2225번: 합분해

첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다.

www.acmicpc.net

높은 정답률(현재 42%)에 비해 개인적으로 푸는데 고생을 좀 했던 문제이다. 총 2가지 풀이법을 소개할 것인데, 1. 내가 이 문제를 처음 푼 방법, 2. 인터넷에서 검색할 수 있는 일반적인(?) 방법이다.

 

N = 5, K = 3일 때를 직접 일일히 세어가면서 구한다고 생각해보자. 일단 2개로 먼저 쪼개보면, (5, 0), (4, 1), (3, 2), (2, 3), (1, 4), (0, 5)가 될 것이다. 여기서 한 번 더 나눠야 하는데, 이 때는 마지막 수를 다시 2개로 쪼갠다고 생각하면 된다. 그러면 (5, 0, 0), (4, 1, 0), (4, 0, 1), (3, 2, 0), (3, 1, 1), (3, 0, 2)... 이 식으로 될텐데 아래 그림을 보면 이해가 될 것이다.

여기서 내가 고려한 점은

1. K를 위와 같은 방식으로 계속 증가시키면서, 마지막 수의 개수를 카운트한다. (마지막 수만 경우의 수에 영향을 미치므로)

2. 마지막 수는 0 ~ N까지의 수인데, K가 증가할 때 임의의 i의 개수는 바로 직전 마지막 수들 중 i보다 큰 수들의 개수를 모두 더한 값이 된다. (위의 그림을 예로 들면, 3의 개수는 바로 직전의 3 ~ 5의 개수를 합친 것과 같다)

 

이를 고려하여 풀이한 소스는 아래와 같다.

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
 
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        
        int[] cnt = new int[n + 1];
        cnt[n] = 1;
        
        for(int i = 2; i <= k; i++) {
            int[] tmp = new int[n + 1];
            tmp[n] = 1;
            
            for(int j = n - 1; j >= 0; j--) {
                tmp[j] = tmp[j + 1] + cnt[j];
                tmp[j] %= 1_000_000_000;
            }
            
            cnt = tmp;
        }
        
        long sum = 0;
        
        for(int i = 0; i <= n; i++) {
            sum += cnt[i];
            sum %= 1_000_000_000;
        }
        
        System.out.println(sum);
    }
}
 
  

 

이번에는 인터넷에서 흔히 볼 수 있는 일반적인(?) 풀이법에 대한 설명이다.

 

N = 5, K = 3일 때를 구한다고 가정해보면, 

0 ~ 5의 수 중 3개를 선택하여 5를 만드는 경우의 수 = 첫번째 수를 0으로 선택하고, 0 ~ 5의 수 중 2개를 선택하여 5를 만드는 경우의 수 + 첫번째 수를 1으로 선택하고, 0 ~ 4의 수 중 2개를 선택하여 4를 만드는 경우의 수 .....

이런 식으로 될텐데, 수식화 해보면 아래와 같다.

 

(N=5, K=3) = (N=5, K=2) + (N=4, K=2) + (N=3, K=2) + (N=2, K=2) + (N=1, K=2) + (N=0, K=2)

 

여기서 우리는 규칙성을 확인할 수 있는데, 이를 다시 수식화 해보면 아래와 같다.

 

(N=i, K=j) = (N=i, K=j-1) + (N=i-1, K=j-1) + (N=i-2, K=j-1) + ..... + (N=0, K=j-1)

<-> (N=i, K=j) = (N=i, K=j-1) + (N=i-1, K=j)

 

위에서 얻어낸 점화식과 함께 아래사항을 초기값으로 이용하면 답을 도출해낼 수 있다.

1. K = 1 일 때 경우의 수는 1이다.

2. N = 1 일 때 경우의 수는 K이다.

 

코드는 아래와 같다.

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
 
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        
        int[][] dp = new int[n + 1][k + 1];
        
        for(int i = 1; i <= k; i++) {
            dp[1][i] = i;
        }
        
        for(int i = 1; i <= n; i++) {
            dp[i][1] = 1;
        }
        
        for(int i = 2; i <= n; i++) {
            for(int j = 2; j <= k; j++) {
                dp[i][j] = (dp[i][j - 1] + dp[i - 1][j]) % 1_000_000_000;
            }
        }
        
        System.out.println(dp[n][k]);
    }
}
  

 

두 코드 모두 동일한 시간복잡도를 가지고 있지만, 개인적으로 두 번째 풀이방법이 더 기억하기도, 이해하기도 쉬운 것 같다. 

 

저작자표시

'알고리즘' 카테고리의 다른 글

백준(BOJ) 2004 : 조합 0의 개수 (JAVA)  (0) 2020.02.04
백준(BOJ) 1697 : 숨바꼭질 (JAVA)  (0) 2020.02.03
백준(BOJ) 1654 : 랜선 자르기 (JAVA)  (0) 2020.01.31
백준(BOJ) 1931 : 회의실배정 (JAVA)  (0) 2020.01.30
백준(BOJ) 1261 : 알고스팟 (JAVA)  (0) 2020.01.29

문제링크 : https://www.acmicpc.net/problem/1654

 

1654번: 랜선 자르기

첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 후 K줄에 걸쳐 이미 가지고 있는 각 랜선의 길이가 센티미터 단위의 정수로 입력된다. 랜선의 길이는 231-1보다 작거나 같은 자연수이다.

www.acmicpc.net

 

결론부터 말하자면, 이 문제는 이분탐색 문제이다. 이분탐색으로 풀면된다는 사실을 알고 이 문제를 보면, 사실 그다지 어려운 문제는 아니다. 근데 이분탐색으로 풀면 되겠다고 생각해내는 것, 그게 어렵다. 어쩌면 그게 알고리즘의 전부일지도 모르겠다...ㅠㅠ

 

그리고 이 문제의 정답비율이 유독 낮은(현재 19%) 이유를 필자가 예상하건데, 함정이 있다. 문제에서는 랜선의 길이가 2^31 -1(int의 최댓값)보다 작거나 같은 자연수라고 나오는데, 이는 랜선의 길이를 int로 해도 되겠다라고 생각하게 만들지만 그렇지 않다. 이분 탐색을 위해 두 길이를 더하는 순간 넘어가버리게 된다... 코드는 아래와 같다.

 

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
 
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int k = Integer.parseInt(st.nextToken());
        int n = Integer.parseInt(st.nextToken());
        int[] wires = new int[k];
        long sum = 0;
        
        for(int i = 0; i < k; i++) {
            wires[i] = Integer.parseInt(br.readLine());
            sum += wires[i];
        }
        
        long answer = 1;
        long left = 1;
        long right = sum / n;
        
        while(left <= right) {
            long mid = (left + right) / 2;
            
            int cnt = checkPossibleLineNo(wires, mid, k);
            
            if(cnt >= n) {
                left = mid + 1;
                
                if(mid > answer) {
                    answer = mid;
                }
            } else {
                right = mid - 1;
            }
        }
        
        System.out.println(answer);
    }
 
    private static int checkPossibleLineNo(int[] wires, long mid, int k) {
        int cnt = 0;
        
        for(int i = 0; i < k; i++) {
            cnt += wires[i] / mid;
        }
        
        return cnt;
    }
}
 
  

 

저작자표시

'알고리즘' 카테고리의 다른 글

백준(BOJ) 1697 : 숨바꼭질 (JAVA)  (0) 2020.02.03
백준(BOJ) 2225 : 합분해 (JAVA)  (0) 2020.02.02
백준(BOJ) 1931 : 회의실배정 (JAVA)  (0) 2020.01.30
백준(BOJ) 1261 : 알고스팟 (JAVA)  (0) 2020.01.29
백준(BOJ) 9466 : 텀 프로젝트 (JAVA)  (0) 2020.01.29

문제링크 : https://www.acmicpc.net/problem/1931

 

1931번: 회의실배정

(1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다.

www.acmicpc.net

 

어떻게 하면 가장 적은 횟수의 비교를 통해 최댓값을 얻어낼 수 있을지를 생각해내는 게 중요한 문제이다. 필자는 처음에 정말 단순하게 '길이(Duration)가 짧은 회의부터 우선적으로 넣으면 되지 않을까?'라고 생각을 했으나, 이 경우에는 회의를 넣어도 되는지 판단하는 시점에서 이미 추가된 "모든" 회의들과 겹치는 부분이 없는지를 비교해야했다. 이 경우의 시간복잡도는 O(N^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
 
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        Meeting[] meetings = new Meeting[n];
        
        for(int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            meetings[i] = new Meeting(start, end);
        }
        
        Arrays.sort(meetings);
        
        int cnt = 1;
        Meeting pastMeeting = meetings[0];
        
        for(int i = 1; i < n; i++) {
            Meeting meeting = meetings[i];
            
            if(!meeting.intersect(pastMeeting)) {
                cnt++;
                pastMeeting = meetings[i];
            }
        }
        
        System.out.println(cnt);
    }
    
    private static class Meeting implements Comparable<Meeting> {
        private int start;
        private int end;
        
        public Meeting(int start, int end) {
            this.start = start;
            this.end = end;
        }
 
        public int getStart() {
            return start;
        }
 
        public int getEnd() {
            return end;
        }
 
        @Override
        public int compareTo(Meeting obj) {
            return this.end - obj.getEnd();
        }
        
        public boolean intersect(Meeting obj) {
            return obj.getStart() < this.end && obj.getEnd() > this.start;
        }
    }
}
 
  

 

상위권 풀이들과 비교해보니, 어째 시간이 좀 더 길게 나왔다. 차이를 분석해보니, 굳이 겹치는(intersect) 여부를 보지 않고, 바로 이전의 end값과 비교시점의 start만 비교하면 되더라. 이 경우에는 오버라이드하는 함수 "compareTo" 에 조건이 일부 추가된다. 그 이유는 길이가 0인 회의들 때문이다. 코드는 아래와 같다.

 

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
 
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        Meeting[] meetings = new Meeting[n];
        
        for(int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            meetings[i] = new Meeting(start, end);
        }
        
        Arrays.sort(meetings);
        
        int cnt = 1;
        int cursor = meetings[0].getEnd();
        
        for(int i = 1; i < n; i++) {
            Meeting meeting = meetings[i];
            
            if(meeting.getStart() >= cursor) {
                cnt++;
                cursor = meeting.getEnd();
            }
        }
        
        System.out.println(cnt);
    }
    
    private static class Meeting implements Comparable<Meeting> {
        private int start;
        private int end;
        
        public Meeting(int start, int end) {
            this.start = start;
            this.end = end;
        }
 
        public int getStart() {
            return start;
        }
 
        public int getEnd() {
            return end;
        }
 
        @Override
        public int compareTo(Meeting obj) {
            int ret = this.end - obj.getEnd();
            
            if(ret == 0) {
                ret = this.start - obj.getStart();
            }
            
            return ret;
        }
    }
}
 
 s

 

저작자표시

'알고리즘' 카테고리의 다른 글

백준(BOJ) 1697 : 숨바꼭질 (JAVA)  (0) 2020.02.03
백준(BOJ) 2225 : 합분해 (JAVA)  (0) 2020.02.02
백준(BOJ) 1654 : 랜선 자르기 (JAVA)  (0) 2020.01.31
백준(BOJ) 1261 : 알고스팟 (JAVA)  (0) 2020.01.29
백준(BOJ) 9466 : 텀 프로젝트 (JAVA)  (0) 2020.01.29

문제링크 : https://www.acmicpc.net/problem/1261

 

1261번: 알고스팟

첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미한다. (1, 1)과 (N, M)은 항상 뚫려있다.

www.acmicpc.net

 

높은 정답률(현재 38%)에 비해 나에게는 정말 어려운 문제였다. 처음에는 DFS와 백트래킹을 이용해 풀어보려고 했으나 시간초과가 나왔다. 그도 그럴 것이 백트래킹의 시간복잡도는 O(2^N)인데, 여기서 주어진 N과 M의 범위를 생각했을 때 최악의 경우 2^10000번의 연산이 필요하다...;;;; 백트래킹을 사용해 아깝게(?) 통과하지 못한 코드는 아래와 같다.

 

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
 
public class Main {
    private static int[] di = {-1, 1, 0, 0};
    private static int[] dj = {0, 0, -1, 1};
    private static int min = Integer.MAX_VALUE;
    private static int m;
    private static int n;
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        m = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());
        
        boolean[][] maze = new boolean[n][m];
        
        for(int i = 0; i < n; i++) {
            char[] temp = br.readLine().toCharArray();
            
            for(int j = 0; j < m; j++) {
                maze[i][j] = temp[j] == '0' ? true : false;
            }
        }
        
        boolean[][] visited = new boolean[n][m];
        
        dfs(maze, visited, 0, 0, 0);
        
        System.out.println(min);
    }
 
    private static void dfs(boolean[][] maze, boolean[][] visited, int i, int j, int cnt) {
        visited[i][j] = true;
        
        if(cnt >= min) {
            return;
        }
        
        if(i == n - 1 && j == m - 1) {
            if(cnt < min) {
                min = cnt;
            }
            
            return;
        }
        
        for(int k = 0; k < 4; k++) {
            int nextI = i + di[k];
            int nextJ = j + dj[k];
            
            if(nextI >= 0 && nextI < n && nextJ >= 0 && nextJ < m && !visited[nextI][nextJ]) {
                if(maze[nextI][nextJ]) {
                    dfs(maze, visited, nextI, nextJ, cnt);
                } else {
                    dfs(maze, visited, nextI, nextJ, cnt + 1);
                }
                
                visited[nextI][nextJ] = false;
            }
        }
    }
}
 
  

 

백트래킹으로는 풀이가 불가능하다는 것을 깨닫고 BFS도 생각해보았으나, 한 번 방문된 곳이 다른 경우의 수에서 또 방문이 가능해야한다는 점을 해결하기 힘들었다. 사실 이 점 때문에 DFS 백트래킹을 처음 생각했던 것이었다. 모든 시점마다 boolean 배열을 추가해서 풀어볼까라는 생각도 해보았으나, 그 경우에는 메모리가 터질 것이었다. 나는 고뇌에 빠졌고, 결국 구글링을 통해 Deque를 이용하면 된다는 사실을 알아냈다. (우오오오오오오!!!)

특정 방에서 다음 방으로 넘어가는 단계에서, 4개의 후보 중 빈방으로 이동하는 것이 그 시점을 기준으로 가장 벽을 최소로 꺨 수 있는 방법일 것이다. 따라서 빈방으로 이동한 시점을 Deque의 앞쪽에 위치시키고(addFirst), 벽을 부순 시점을 Deque의 뒷쪽에 위치시킴으로써(addLast) 빈방으로 이동한 시점에 무조건 우선순위를 주게되면 굳이 visited에 대해 고민할 필요가 없어진다. 한 번 방문했을 때의 벽을 부순 횟수가 무조건 최소값이 되기 때문이다. 코드는 아래와 같다.

 

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
 
public class Main {
    private static int[] di = {1, -1, 0, 0};
    private static int[] dj = {0, 0, 1, -1};
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int m = Integer.parseInt(st.nextToken());
        int n = Integer.parseInt(st.nextToken());
        
        boolean[][] isEmpty = new boolean[n][m];
        
        for(int i = 0; i < n; i++) {
            char[] temp = br.readLine().toCharArray();
            
            for(int j = 0; j < m; j++) {
                if(temp[j] == '0') {
                    isEmpty[i][j] = true;
                }
            }
        }
        
        int min = bfs(isEmpty, n, m);
        
        System.out.println(min);
    }
    
    private static int bfs(boolean[][] isEmpty, int n, int m) {
        boolean[][] visited = new boolean[n][m];
        visited[0][0] = true;
        Deque<Point> deque = new ArrayDeque<Point>();
        deque.offer(new Point(0, 0, 0));
        
        while(!deque.isEmpty()) {
            Point poll = deque.poll();
            int i = poll.getI();
            int j = poll.getJ();
            int cnt = poll.getCnt();
            
            if(i == n - 1 && j == m - 1) {
                return cnt;
            }
            
            for(int k = 0; k < 4; k++) {
                int nextI = i + di[k];
                int nextJ = j + dj[k];
                
                if(nextI >= 0 && nextJ >= 0 && nextI < n && nextJ < m && !visited[nextI][nextJ]) {
                    visited[nextI][nextJ] = true;
                    
                    if(isEmpty[nextI][nextJ]) {
                        deque.addFirst(new Point(nextI, nextJ, cnt));
                    } else {
                        deque.addLast(new Point(nextI, nextJ, cnt + 1));
                    }
                }
            }
        }
        
        return -1;
    }
 
    private static class Point {
        private int i;
        private int j;
        private int cnt;
        
        public Point(int i, int j, int cnt) {
            this.i = i;
            this.j = j;
            this.cnt = cnt;
        }
 
        public int getI() {
            return i;
        }
 
        public int getJ() {
            return j;
        }
 
        public int getCnt() {
            return cnt;
        }
    }
}
  

 

끝으로, 이 문제를 다 풀고 나니 알고리즘 분류가 '다익스트라 알고리즘'으로 되어있는 것을 알 수 있었다. 올바른 방법으로 풀었는지는 알 수 없으나;; 참고 삼아 공유해본다. 코드는 아래와 같으며, 다익스트라 알고리즘에 대해 참고했던 사이트 링크를 남긴다.  https://mattlee.tistory.com/50

 

<dijkstra의 최단="" 경로="" 알고리즘=""> 기본개념과 알고리즘</dijkstra의>

# 최단 경로 최단 경로(shortest path)문제는 정점 u와 정점 v를 연결하는 경로 중 간선들의 가중치 합이 최소가 되는 경로를 찾는 문제다. 간선의 가중치는 경우에 따라 비용, 거리, 시간 등으로 해석될 수 있다...

mattlee.tistory.com

 

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
 
public class Main {    
    private static int[] di = {1, 0, -1, 0};
    private static int[] dj = {0, 1, 0, -1};
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int m = Integer.parseInt(st.nextToken());
        int n = Integer.parseInt(st.nextToken());
        
        if(m == 1 && n == 1) {
            br.readLine();
            System.out.println(0);
            return;
        }
        
        boolean[][] visited = new boolean[n][m];
        short[][][][] wallInfo = new short[n][m][n][m];
        
        short[][] map = new short[n][m];
        
        for(int i = 0; i < n; i++) {
            char[] row = br.readLine().toCharArray();
            
            for(int j = 0; j < m; j++) {
                map[i][j] = (short) (row[j] - 48);
            }
        }
        
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                for(int k = 0; k < n; k++) {
                    for(int h = 0; h < m; h++) {
                        wallInfo[i][j][k][h] = 10000;
                    }
                }
            }
        }
        
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                for(int k = 0; k < 4; k++) {
                    int newI = i + di[k];
                    int newJ = j + dj[k];
                    
                    if(newI >= 0 && newI < n && newJ >= 0 && newJ < m) {
                        wallInfo[i][j][newI][newJ] = map[newI][newJ];
                    }
                }
            }
        }
        
        visited[0][0] = true;
        short[][] distance = wallInfo[0][0];
        
        while(true) {
            int minI = Integer.MAX_VALUE;
            int minJ = Integer.MAX_VALUE;
            int min = Integer.MAX_VALUE;
            
            for(int a = 0; a < n; a++) {
                for(int b = 0; b < m; b++) {    
                    if(!visited[a][b] && distance[a][b] < min) {
                        min = distance[a][b];
                        minI = a;
                        minJ = b;
                    }
                }
            }
            
            if(minI == n - 1 && minJ == m - 1) {
                break;
            }
            
            visited[minI][minJ] = true;
            
            for(int a = 0; a < n; a++) {
                for(int b = 0; b < m; b++) {
                    if(!visited[a][b]) {
                        if(distance[a][b] > distance[minI][minJ] + wallInfo[minI][minJ][a][b]) {
                            distance[a][b] = (short) (distance[minI][minJ] + wallInfo[minI][minJ][a][b]);
                        }
                    }                
                }
            }
        }
        
        System.out.println(distance[n - 1][m - 1]);
    }
}
 
 
  

 

 

'알고리즘' 카테고리의 다른 글

백준(BOJ) 1697 : 숨바꼭질 (JAVA)  (0) 2020.02.03
백준(BOJ) 2225 : 합분해 (JAVA)  (0) 2020.02.02
백준(BOJ) 1654 : 랜선 자르기 (JAVA)  (0) 2020.01.31
백준(BOJ) 1931 : 회의실배정 (JAVA)  (0) 2020.01.30
백준(BOJ) 9466 : 텀 프로젝트 (JAVA)  (0) 2020.01.29

문제링크 : https://www.acmicpc.net/problem/9466

 

9466번: 텀 프로젝트

문제 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 수도 있다. 프로젝트 팀을 구성하기 위해, 모든 학생들은 프로젝트를 함께하고 싶은 학생을 선택해야 한다. (단, 단 한 명만 선택할 수 있다.) 혼자 하고 싶어하는 학생은 자기 자신을 선택하는 것도 가능하다. 학생들이(s1, s2, ..., sr)이라 할 때, r=

www.acmicpc.net

각 노드를 연결했을 때, 순환사이클에 속하지 못하는 노드의 갯수를 구하는 문제이다.

첫번째 풀이를 할 때 고려한 점은 다음과 같다.

1. 누구의 선택도 받지 못한 학생부터 탐색(dfs)을 시작해서 중복 탐색을 제거한다.
2. 순환사이클안에 포함된 노드만 두 번 이상 탐색이 될 것이다.
3. 누구의 선택도 받지 못한 학생에서만 탐색을 시작하기 때문에, 폐쇄된(곁가지가 없는) 순환사이클을 이루는 노드들의 경우(예: 1-> 2-> 3 -> 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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
 
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        StringBuffer sb = new StringBuffer();
        
        for(int i = 0; i < t; i++) {
            int n = Integer.parseInt(br.readLine());
            int[] selectedIdx = new int[n + 1];
            boolean[] chosen = new boolean[n + 1];
            StringTokenizer st = new StringTokenizer(br.readLine());
            
            for(int j = 1; j <= n; j++) {
                selectedIdx[j] = Integer.parseInt(st.nextToken());
                chosen[selectedIdx[j]] = true;
            }
            
            boolean[] visited = new boolean[n + 1];
            boolean[] revisited = new boolean[n + 1];
            
            for(int j = 1; j <= n; j++) {
                if(!chosen[j]) {
                    boolean[] localVisited = new boolean[n + 1];
                    dfs(selectedIdx, j, localVisited, visited, revisited);
                }
            }
            
            int cnt = 0;
            
            for(int j = 1; j <= n; j++) {
                if(visited[j] && !revisited[j]) {
                    cnt++;
                }
            }
            
            sb.append(cnt + "\n");
        }
        
        System.out.println(sb);
    }
 
    private static void dfs(int[] selectedIdx, int j, boolean[] localVisited, boolean[] visited, boolean[] revisited) {
        if(localVisited[j]) {
            revisited[j] = true;
        } else {
            visited[j] = true;
            localVisited[j] = true;
        }
        
        if(!revisited[selectedIdx[j]]) {
            dfs(selectedIdx, selectedIdx[j], localVisited, visited, revisited);
        }
    }
}
  

하지만 이 경우, 이미 순환임이 체크된 사이클에 대해 중복된 탐색이 이루어질 수 있는 여지가 있다.

 

필자의 그림 실력을 이해바라며...;; 1번으로 탐색 후에 2번으로 탐색할 경우, 위의 코드로는 또 한번 순환사이클을 체크해야한다.

 

따라서 두 번째로 문제를 풀 때는 다음과 같은 점을 고려했다.

 

1. 순환사이클에 포함되지 않는 노드를 세는 것이 아니라, 순환사이클에 속하는 노드의 갯수를 센 다음 전체에서 빼면 된다.

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
 
public class Main {    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        StringBuffer sb = new StringBuffer();
        
        for(int i = 0; i < t; i++) {
            int n = Integer.parseInt(br.readLine());
            int[] selectedIdx = new int[n + 1];
            boolean[] chosen = new boolean[n + 1];
            StringTokenizer st = new StringTokenizer(br.readLine());
            
            for(int j = 1; j <= n; j++) {
                selectedIdx[j] = Integer.parseInt(st.nextToken());
                chosen[selectedIdx[j]] = true;
            }
            
            Test test = new Test(selectedIdx, chosen, n);
            
            
            sb.append(test.solve() + "\n");
        }
        
        System.out.println(sb);
    }
    private static class Test {
        private int[] selectedIdx;
        private boolean[] chosen;
        private int n;
        private int teamCnt = 0;
        
        public Test(int[] selectedIdx, boolean[] chosen, int n) {
            this.selectedIdx = selectedIdx;
            this.chosen = chosen;
            this.n = n;
        }
 
        public int solve() {
            boolean[] visited = new boolean[n + 1];
            boolean[] resolved = new boolean[n + 1];
            
            for(int j = 1; j <= n; j++) {
                if(!chosen[j] && !resolved[j]) {
                    dfs(selectedIdx, j, visited, resolved);
                }
            }
                        
            for(int j = 1; j <= n; j++) {
                if(!visited[j]) {
                    teamCnt++;
                }
            }
            
            return n - teamCnt;
        }
        
        private void dfs(int[] selectedIdx, int j, boolean[] visited, boolean[] resolved) {
            visited[j] = true;        
            int next = selectedIdx[j];
            
            if(!visited[next]) {
                dfs(selectedIdx, next, visited, resolved);
            } else {
                
                if(!resolved[next]) {
                    
                    for(int i = next; i != j; i = selectedIdx[i]) {
                        teamCnt++;
                    }
                    
                    teamCnt++;
                }            
            }
            
            resolved[j] = true;
        }
    }    
}
 
  

필자는 항상 알고리즘 문제를 풀고나면, 내 소스의 걸린 시간 및 메모리를 상위권 사람들과 비교하면서 내가 올바르게 풀었는지의 여부를 판단하는데, 상위권 소스와 같은 로직을 썼음에도 불구하고 시간이 그 사람들처럼 줄어들지 않아서 차이점을 살펴보니, static class를 선언한 후 인스턴스 메서드를 사용하는 것이었다. 구글링을 통해 이유를 검색해보았으나 아직 찾질 못하였으니 혹시 아는 분은 댓글 남겨주시길 간절히 바라옵니다...^^;

 

 

'알고리즘' 카테고리의 다른 글

백준(BOJ) 1697 : 숨바꼭질 (JAVA)  (0) 2020.02.03
백준(BOJ) 2225 : 합분해 (JAVA)  (0) 2020.02.02
백준(BOJ) 1654 : 랜선 자르기 (JAVA)  (0) 2020.01.31
백준(BOJ) 1931 : 회의실배정 (JAVA)  (0) 2020.01.30
백준(BOJ) 1261 : 알고스팟 (JAVA)  (0) 2020.01.29

+ Recent posts

티스토리툴바