(Java) SWEA 7964. 부먹왕국의 차원관문

알고리즘 스터디에서 푼 지는 꽤 됐지만 알고리즘과 백엔드 공부에 정신없이 치여 살다가 이제야 기록하는 문제풀이 ..! 

오늘부터 1일 최소 1문제풀이 글 작성 꼭꼭 하자 :) 

---

1. 문제 조건 분석하기

 

- 입력

테스트 케이스 수 T

N : N개의 부먹왕국 도시수  / D: 이동제한 거리

각 도시에 차원관문이 남아있는지를 표현하는 수(1은 연결, 0은 파괴)

 

- 문제 설명

부먹왕국 도시들이 이동제한 거리 내에서 관문에서 다른 관문으로 이동 가능하며, 모든 도시들이 이동 가능하도록 관문을 얼마나 추가로 설치해야 하는지를 계산해야 한다.

 

** 주의 ** 

모든 차원 관문 사이와 직접적으로 이동 가능하도록 해야한다는 조건이 있음을 주의해야 한다. 

예를 들어 D=1 일 때는, 모든 도시에 관문이 설치되어야 관문에서 관문으로 거리 1이내에 이동 가능하다. 

D=2 일 때는 관문과 관문 사이에 관문이 없는 도시는 최대 1개만 존재할 수 있다.(그래야 모든 도시 이동 가능)

 

2. 아이디어

=> 관문이 필요한 도시를 체크하기 위해 관문이 있는 도시부터 D-1개가 넘게 관문이 파괴된 도시를 셈으로써 관문을 세워야할 도시의 수를 구할 예정.

- 도시들의 상태를 배열에 입력하기 

- 도시들을 for문으로 돌며 관문이 있는지 체크하기

- 관문이 있다면 이후부터 관문이 없는 도시들의 개수를 체크하다가 D가 됐음에도 관문이 없다면 결과값을 1 더할 것.

 

 

 

3. 구현

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

public class SE_7964부먹왕국 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		int T = Integer.parseInt(br.readLine());
		
		for(int t=1; t<=T; t++) {
			st = new StringTokenizer(br.readLine());
			int N = Integer.parseInt(st.nextToken());
			boolean[] doors = new boolean[N+2];
			int D = Integer.parseInt(st.nextToken());
		
			st = new StringTokenizer(br.readLine());
			
			doors[0] = true;
			doors[N+1] = true;
			
			for(int n=1; n<=N; n++) {
				if(Integer.parseInt(st.nextToken())==1) 	doors[n] = true;

				}

			int cnt =0;
			int result =0;
		
			for(int n=1; n<=N+1; n++) {
				
				if(doors[n]) {
					if(cnt >= D) {
						result += cnt/D;
					}
					cnt =0;
				
				}
				else if(!doors[n]) {
					cnt ++;
				}
			}
			System.out.printf("#%d %d\n", t, result);
		}
	}
}