[Gold V][JAVA]2138번:전구와스위치

2138번:전구와스위치

문제 요약

• 0이면 꺼진 전구, 1이면 켜진 전구를 의미하는 전구들의 상태 A, B가 주어진다.
• i번째 전구 스위치를 누르면, i-1, i, i+1 3개의 인접한 전구의 상태가 바뀐다.
• A 상태를 B 상태로 바꾸기 위해 스위치를 최소 몇번 눌러야 하는지 구해야 한다.
• 바꾸는 것이 불가능할 수 있으며 이 경우 -1을 출력한다.

예제

N = 3
A = 000
B = 010
1. A의 0번 스위치를 누르면 110 으로 상태가 변한다
2. A의 1번 스위치를 누르면 001 으로 상태가 변한다.
3. A의 2번 스위치를 누르면 010 으로 상태가 변한다.
총 3번 스위치를 눌렀고, A 상태에서 B 상태로 변경되었으므로 답은 3이다. (3보다 적게 누를 수 없음)

풀이

1. 전구를 누르는 순서는 상관이 없다.

가령 위의 예제에서 1->0->2 순으로 누르거나, 2->1->0으로 눌러도 똑같은 상태가 된다.

즉 누르는 순서를 신경쓸 필요 없이 0번 스위치부터 N-1번 스위치까지 순차적으로 돌면서 해당 스위치를 눌러도 될지 말지만 결정하면 된다.

2. 순차적으로 탐색한다면 i번째 스위치가 i-1번째 전구의 상태를 결정할 마지막 스위치이다.

다시 예제를 보자

A = 000
B = 010

0번째 스위치를 누른 경우

0번째 스위치를 누른 경우 A는 110이다.
1번째 스위치에서는 반드시 스위치를 눌러야한다. 왜냐하면 A와 B가 같기 위해서는 A[0] = B[0] = 0이어야 하는데, 현재 110 상태에서 스위치를 누르지 않고 지나가면 A[0]이 영원히 1이 되기 때문이다.
1번째 스위치를 눌렀다면 A는 001이다.
2번째 스위치 역시 반드시 스위치를 눌러야한다. A[1] = B[1] = 1이 되어야 하는데 현재 A[1] = 0이기 때문이다.

0번째 스위치를 누르지 않은 경우

0번째 스위치를 누른 경우 A는 000이다.
1번째 스위치에서는 반드시 스위치를 누르지 않아야 한다. 1번 스위치를 누르면 A[0] 값이 영원히 1이 되기 때문이다. 여전히 A의 상태는 000이다.
반대로 2번째 스위치는 반드시 눌러야한다. A[1] 값이 1이 되어야 하기 때문이다. 그러나 2번째 스위치를 누르면 A의 상태는 011이 되어 A != B이다.

결론

즉 0번째 스위치만 누를지 말지만이 경우의 수이며, 나머지는 모두 A[i-1], B[i-1] 값에 따라 고정된다.
이를 코드로 구현하면 된다.

[JAVA]

charAt(i) -'0' 사용 이유 : 문자열 -> 정수형

정답

import java.io.BufferedReader;
 import java.io.IOException;
 import java.io.InputStreamReader;
 import java.util.Arrays;

 public class Main {  //문제유형: 그리디 , 메모리 제한: 128MB, 시간 제한: 2초
     public static void main(String args[]) throws IOException {
         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
         int n = Integer.parseInt(br.readLine());
         String s1 = br.readLine(); //현재 상태
         String s2 = br.readLine(); //원하는 상태

         int[] a = new int[n];
         for (int i = 0; i < n; i++) a[i] = s1.charAt(i) - '0'; // a는 0번 스위치를 안누른 경우
         int[] b = new int[n];
         for (int i = 0; i < n; i++) b[i] = s2.charAt(i) - '0';

         int[] c = Arrays.copyOf(a, n); // c는 0번째 스위치를 누른 경우
         c[0] = 1 - c[0]; // 0번째 스위치를 누르지 않은 경우
         c[1] = 1 - c[1]; //0번째 스위치를 누른 경우

         int answer = solve(n, a, b);
         int answer2 = solve(n, c, b);
         if (answer2 != -1) answer2++;

         if (answer == -1)
             System.out.println(answer2);
         else if (answer2 == -1)
             System.out.println(answer);
         else
             System.out.println(Math.min(answer2, answer));
     }

     static int solve(int n, int[] a, int[] b) {
         int cnt = 0;

         for (int i = 0; i < n - 1; i++) {
             if (a[i] != b[i]) {
                 cnt++;
                 a[i] = 1 - a[i];
                 a[i + 1] = 1 - a[i + 1];
                 if (i != n - 2)
                     a[i + 2] = 1 - a[i + 2];
             }
         }
         return a[n - 1] != b[n - 1] ? -1 : cnt;
     }
 }