알고리즘 문제

백준 2138번) 전구와 스위치 (JAVA)

roder 2022. 10. 3. 13:34

문제

N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져 있는 상태와 꺼져 있는 상태 중 하나의 상태를 가진다. i(1 < i < N)번 스위치를 누르면 i-1, i, i+1의 세 개의 전구의 상태가 바뀐다. 즉, 꺼져 있는 전구는 켜지고, 켜져 있는 전구는 꺼지게 된다. 1번 스위치를 눌렀을 경우에는 1, 2번 전구의 상태가 바뀌고, N번 스위치를 눌렀을 경우에는 N-1, N번 전구의 상태가 바뀐다.

N개의 전구들의 현재 상태와 우리가 만들고자 하는 상태가 주어졌을 때, 그 상태를 만들기 위해 스위치를 최소 몇 번 누르면 되는지 알아내는 프로그램을 작성하시오.

 

입력

첫째 줄에 자연수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 전구들의 현재 상태를 나타내는 숫자 N개가 공백 없이 주어진다. 그 다음 줄에는 우리가 만들고자 하는 전구들의 상태를 나타내는 숫자 N개가 공백 없이 주어진다. 0은 켜져 있는 상태, 1은 꺼져 있는 상태를 의미한다.

출력

첫째 줄에 답을 출력한다. 불가능한 경우에는 -1을 출력한다.

예제 입력 1 복사

3
000
010

예제 출력 1 복사

3

알고리즘 분류

 

 

#풀이방법

처음에 전구를 어떻게 해야 하는지 감을 잡지 못했다.

마음같아서는 완전탐색과 백트래킹으로 돌려 모든 경우의 수를 탐색하고 싶은 욕망이 있었지만 , 

분명히 시간초과 될 것이 뻔했고, 또 알고리즘이 그리디 알고리즘이기 때문에 완전탐색으로 돌려서는 안된다.

 

따라서 전체 전구를 처음부터 끝까지 for문으로 차례대로 탐색해야한다.

탐색을 하다보면 여기서 발견되는 중요한 한가지가 있다.

어떤 임의의 인덱스를 i라고 가정한다면, i를 누를 경우, i-1,i,i+1 3가지가 바뀌게 되는데

처음부터 끝까지 탐색하는 경우,  i-1은 한번 확정이 되어 우리가 임의로 바꿀 수 없게 된다.

 

따라서 배열[i-1]을 목표와 비교하여 누를지 말지를 결정하면 된다.

 

또한 탐색하는 경우는 2가지가 있다.

 

첫번째 첫번째 스위치를 누르고 갈 것인가?

두번째 첫번째 스위치를 누르지 않고 갈 것인가?

이 두가지로 나뉠 수 있다.

 

이 두가지 경우의수를 비교하여 최소로 누른 숫자를 Math.min을 이용하여 비교한 후, 출력하면 된다.

 

목표 전구와 같은지 확인하기 위해서는

배열 끝에 전구가 목표 전구와 동일한지 체크해주면 된다.

 

 

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
public static int search(char[] p,char[] goal,int N) {
        
        int cnt = 0;
        
        for(int i=1; i<N; i++) {
            
            if(p[i-1] != goal[i-1]) {
                
                cnt++;//스위치 누른 횟수 +1
                
                for(int j=i-1; j<=i+1; j++) {
                    
                    if(j == N)
                        break;
                    
                    if(p[j] == '0')
                        p[j] = '1';
                    else
                        p[j] = '0';
                    
                }//목표와 다를 경우 스위치를 눌러 모든 스위치의 방향을 변경시켜준다.
                
            }
            
        }
        
        
        
        if(p[N-1] == goal[N-1]) {
            return cnt;
        }//목표 전구와 같은지 확인
        else {
            return INF;
        }
        
        
        
    }
cs

 

이처럼 처음 전구와 목표 전구의 i-1만 비교하여 누를지 말지를 결정하고,

마지막 인덱스의 전구가 목표 전구와 동일한지 판단한다면,

한번의 for문을 통해 그리디적으로 문제를 해결 할 수 있다.

 

 

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
import java.util.*;
//1t
 
public class Main {
    
    static final int INF = 9999999;//스위치를 누른 최대 횟수
    
 
    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        
        int N = sc.nextInt();
        
        char[] cur = sc.next().toCharArray();
        char[] goal = sc.next().toCharArray();
        
        char[] noPress = cur.clone();
        char[] press = cur.clone();
        
        int cnt = INF;
        
        //첫번째 스위치를 누르지 않는 경우
        
        
        cnt = Math.min(cnt,search(noPress,goal,N));
        
    
        //첫번째를 누르는 경우,
        for(int i=0; i<=1; i++) {
            
            if(press[i] == '1')
                press[i] = '0';
            else
                press[i] = '1';
        }
        
    
        cnt = Math.min(cnt,search(press,goal,N)+1);
        
        
        if(cnt == INF)
            System.out.println(-1);
        else
            System.out.println(cnt);
        
        
    }
    
    public static int search(char[] p,char[] goal,int N) {
        
        int cnt = 0;
        
        for(int i=1; i<N; i++) {
            
            if(p[i-1] != goal[i-1]) {
                
                cnt++;//스위치 누른 횟수 +1
                
                for(int j=i-1; j<=i+1; j++) {
                    
                    if(j == N)
                        break;
                    
                    if(p[j] == '0')
                        p[j] = '1';
                    else
                        p[j] = '0';
                    
                }//목표와 다를 경우 스위치를 눌러 모든 스위치의 방향을 변경시켜준다.
                
            }
            
        }
        
        
        
        if(p[N-1] == goal[N-1]) {
            return cnt;
        }//목표 전구와 같은지 확인
        else {
            return INF;
        }
        
        
        
    }
        
    
    
 
}
cs