https://www.acmicpc.net/problem/2138
2138번: 전구와 스위치
N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져 있는 상태와 꺼져 있는 상태 중 하나의 상태를 가진다. i(1 < i < N)번 스위치를 누르면 i-1, i, i+1의 세 개의 전구의 상태가 바뀐다. 즉, 꺼져
www.acmicpc.net
코드설명
그리디 문제입니다.
이 문제에서 핵심로직은,
1. i의 스위치를 누르면 ( i - 1 , i, i + 1 ) 이렇게 3개의 스위치가 변화됩니다. 이 경우 고려해야할 것이 너무 많습니다.
- 그러므로, i의 스위치 위치에서 i-1 번과 우리가 목표로 하고자하는 전구의 i-1 번쨰 모양을 비교하고,
- 현재 전구의 모양 i - 1 번과 , 목표 전구의 i - 1이 다르다면, i 번쨰 스위치를 누름으로써 최대한 그리디하게 진행합니다.
2. 위의 로직처럼 i-1 만을 비교하여 i번 스위치를 누를경우, 만약 0번쨰 스위치인경우 1번쨰 스위치를 누르는 경우로만 변경됩니다. 그러므로, 0번째 스위치를 한번 클릭하여 진행합니다. ( 이때, 클릭 숫자를 하나 증가시켜야 합니다. )
위의 2가지 로직을 통해 구현할 수 있습니다.
이 문제에서 i-1 번째 스위치를 한번만 바꾸기 위하여 i번째 스위치를 통해서만 바꾸는 생각을 해야 할 수 잇습니다.
코드
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Main { public static int N; public static int[] arr1; public static int[] arr2; public static int[] target; public static int switchCnt1 = 0, switchCnt2 = 0; public static int answer = Integer.MAX_VALUE; public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); N = Integer.parseInt(st.nextToken()); arr1 = new int[N]; arr2 = new int[N]; target = new int[N]; st = new StringTokenizer(br.readLine()); String s = st.nextToken(); for(int i=0;i<N;i++) { arr1[i] = Integer.parseInt(String.valueOf(s.charAt(i))); arr2[i] = arr1[i]; } st = new StringTokenizer(br.readLine()); s = st.nextToken(); for(int i=0;i<N;i++) { target[i] = Integer.parseInt(String.valueOf(s.charAt(i))); } //arr2의 0번쨰 스위치를 누르는 경우 arr2[0] = arr2[0] == 1 ? 0 : 1; arr2[1] = arr2[1] == 1 ? 0 : 1; switchCnt2 += 1; //0번째는 검사안하고, 1번째부터 검사합니다. ( 0 번째는 arr2에서만 누르고 작동합니다. ) for(int i=1;i<N;i++) { if(arr1[i-1] != target[i-1]) { if( i == N - 1 ) { //만약 마지막 전구를 검사한다면, 2개가 바뀌므로 arr1[i-1] = arr1[i-1] == 1 ? 0 : 1; arr1[i] = arr1[i] == 1 ? 0 : 1; } else { // i번쨰 스위치 누를시 ( 좌, 현재위치, 우 )의 전구가 변합니다. arr1[i-1] = arr1[i-1] == 1 ? 0 : 1; arr1[i] = arr1[i] == 1 ? 0 : 1; arr1[i+1] = arr1[i+1] == 1 ? 0 : 1; } switchCnt1 += 1; } if(arr2[i-1] != target[i-1]) { // i-1 번째가 target과 다르다면, i 번쨰에서 변경해주어야합니다. if( i == N - 1 ) { //만약 마지막 전구를 검사한다면, 2개가 바뀌므로 arr2[i-1] = arr2[i-1] == 1 ? 0 : 1; arr2[i] = arr2[i] == 1 ? 0 : 1; } else { // i번쨰 스위치 누를시 ( 좌, 현재위치, 우 )의 전구가 변합니다. arr2[i-1] = arr2[i-1] == 1 ? 0 : 1; arr2[i] = arr2[i] == 1 ? 0 : 1; arr2[i+1] = arr2[i+1] == 1 ? 0 : 1; } switchCnt2 += 1; } } for(int i=0;i<N;i++) { if(arr1[i] != target[i]) { switchCnt1 = Integer.MAX_VALUE; } if(arr2[i] != target[i]) { switchCnt2 = Integer.MAX_VALUE; } } int answer = Math.min(switchCnt1, switchCnt2); if(answer == Integer.MAX_VALUE) { System.out.println("-1"); }else { System.out.println(answer); } } }
'알고리즘 > 백준' 카테고리의 다른 글
[백준] 1987 알파벳 - Backtracking(백트래킹) + DFS(깊이우선탐색) + HashSet(해시셋) JAVA (0) | 2023.08.12 |
---|---|
[백준] 7490 0 만들기 - 완전탐색 + 문자열 + stringtokenizer JAVA (0) | 2023.08.11 |
[백준] 14719 빗물 - 구현 + 시뮬레이션 JAVA (0) | 2023.08.10 |
[백준] 2493 탑 - 자료구조 Stack(스택) JAVA (0) | 2023.08.10 |
[백준] 20055 컨베이어 벨트 위의 로봇 - 구현 + 시뮬레이션 JAVA (0) | 2023.08.10 |