[swea-D3] 2550. 징검다리도 두드려보고 건너라

# [swea-D3] 2550. 징검다리도 두드려보고 건너라

문제

리라의 명수 오르페우스는 에우리디케와 사랑에 빠져 결혼하였다. 하지만 결혼한 지 얼마 되지 않아 에우리디케는 산책을 나갔다가 자신에게 추근대는 양치기를 급히 피해 도망치다 뱀에게 물려 죽고 말았다. 오르페우스는 아내를 이승으로 다시 데려 오겠다고 결심하고 저승으로 내려갔다.

저승에는 기억을 잃는 레테의 강이 있었는데 건너기 위해서는 돌 N(1 <= N <= 1000)개로 이루어진 신비한 징검다리를 지나야 한다. 또한, 이 징검다리의 N개의 돌들은 각각 처음에는 물 속에 가라 앉아 있거나 건널 수 있도록 떠있는 두가지의 불규칙적인 상태를 가진다. 이 돌들은 리라연주를 들려주면 바라보고 있는 방향으로 다음 돌부터 연속한 K(1 <= K <= min(N, 100))개의 돌들은 반대의 상태가 된다. 또 현재 서 있는 돌은 M (1 <= M <= 5)번의 연주를 들으면 점점 가라 앉기 때문에 한 곳에서 M번 이상의 연주를 할 수 없다.

(오르페우스는 맨 처음 육지 위에 서있고, 그 육지는 돌이 아니므로 가라앉지 않는다) (앞으로 혹은 뒤로 한 칸씩 이동이 가능하며, 이동하기 위해서는 다음 징검다리의 돌은 떠있어야 한다) (징검다리 위에는 한 사람만 서있을 수 있기 때문에, 에우리디케를 위해서 징검다리의 돌들은 모두 떠있어야 한다)

사랑하는 아내를 구하려는 오르페우스를 프로그래머인 당신이 도와주도록 하자. 만약 강을 건널 수 있는지 판단하고, 강을 건널 수 있다면 오르페우스가 해야 하는 리라연주의 최소 횟수를 구하여 알려주어라.

(물에 닿으면 기억을 잃기 때문에 M번 연주 후에 반드시 다른 곳으로 이동하여야 한다)

Input

입력 첫 줄에는 테스트 케이스 개수 T(1<= T <= 100)이 주어진다.

그 다음 줄부터 테스트 케이스 T개가 온다. 각 테스트 케이스는 모두 2 줄로 구성되어 있다. 각 테스트 케이스 첫 번째 줄에는 현재 징검다리의 상태가 ‘1’ 혹은 ‘0’ N개(1<= N<= 1000) 문자열로 주어진다 (* 1이면 현재 떠있는 상태, 0이면 가라 앉아 있는 상태) 각 테스트 케이스 두 번째 줄에는 연주에 반응 하는 돌의 개수 K (1 <= K <= min(N, 100))와 한 곳에 서 할 수 있는 최대 연주 횟수 M (1 <= M <= 5)가 공백을 사이에 두고 차례로 주어진다.

Output

강을 건널 수 없을 때, -1 출력 강을 건널 수 있을 때, 최소 리라 연주 횟수 출력

Hints

입력

3
1100100
3 2
11101
2 3
011111110
4 1

출력

#1 2
#2 -1
#3 4

🙋‍♂️ 들어가며

돌 뒤집기랑 유사하다

조건을 정리하자

• 한 곳에서 M 번이상 연주 X
• 특정돌 위치 + (K-1)개 까지 연속 변환

❗잠깐

어차피 0일때 해당위치부터 해당위치+K 까지 1번만 바꾸니까

한 곳에서 M번 이상 연주는 자동으로 안하게 된다.

속임수였던 것이다.

이제 코드를 보자

✅ 코드

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


public class Solution {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		
		for (int tc = 1; tc < T+1; tc++) {
			String num_arr = br.readLine();
			String[] KM = br.readLine().split(" ");
			
			int N = num_arr.length();
			int[] arr = new int[N];
			for (int i = 0; i < N; i++) {
				arr[i] = num_arr.charAt(i) - '0';
			}
			int K = Integer.parseInt(KM[0]);
			int M = Integer.parseInt(KM[1]);
			
			
			// 1. 횟수, 범위 (j ~ j+K) 만큼 연속 변경 가능한지?
			int cnt = 0;
			boolean success = true;
			
			// 2. 검사
			for (int i = 0; i < N; i++) {
				if (arr[i] == 0) {
					for (int j = i; j < i+K; j++) {
						// 2-1. 가지치기
						if (j >= N) {
							success = false;
							break;
						}
						
						// 2-2. 숫자 뒤집기
						if (arr[j] == 0) {
							arr[j] = 1;
						}
						else if (arr[j] == 1) {
							arr[j] = 0;
						}
						
					}
					
					// 2-3. 가지치기
					if (!success) break;
					
					// 2-4. 횟수 추가
					cnt++;
				}
			}
			
			
			
			
			
			// 4. 출력
			if (success) {
				System.out.println("#" + tc + " " + cnt);
			}
			else if (!success) {
				System.out.println("#" + tc + " " + -1);
			}
			
			
			
			
		}
		
	}
}