[SWEA] 7964. 부먹왕국의 차원 관문

문제

부먹 왕국은 찍먹 무리에게 침략을 당했었다.

하지만 탕수육의 힘으로 성공적으로 막아 내었으나 도시의 많은 차원관문이 파괴당했다.

부먹 왕국의 특징은 모든 도시들을 건설 할 때 일렬로 이어지게 만들었다.

어느 도시에 차원 관문을 설치하면 그 도시와 거리 D 이하인 다른 도시에서 차원 관문이 있는 곳으로 들어오거나, 혹은 차원 관문에서 거리 D 이하인 다른 도시로 나가는것이 가능하다.

찍먹 왕국의 재침공에 대비하기 위해서 모든 도시 이동이 되어야하며 모든 차원 관문 사이와 직접적으로 이동이 가능하도록 차원 관문을 재건하려고 한다.
(단, 0번 위치와 N+1번 위치에는 차원 관문이 존재 한다.)

가능한 빠른 건설을 위하여 최소 개수로 설치하는 계획을 세우려고 할때

도시들마다 차원관문이 남아있는 지에 대한 정보가 주어졌을 때, 이동에 필요한 차원관문의 최소 개수를 구하여라.

 

풀이방법

인접한 도시들이 있을 때 각 도시들은 최소 m크기마다 차원의 문이 존재해야한다.

 

예를 들어 도시들의 정보 1 0 0 0 0 1와 m = 2가 주어졌다면,

 

1 0 1 0 1 1 로 되어야한다. 즉 차원의 문은 최소한 2개가 설치되어야한다.

 

각 도시들의 정보가 주어졌을 때, 이를 1차원 배열로 받는다. 배열은 1과 0으로 이루어져있다.

 

1 사이에는 m-1개의 0만 존재할 수 있도록 배열을 만들어주고 그렇게 만들어 주기 위해서 1을 대입한 수를 카운트한다.

 

소스코드

package samsung;

import java.util.*;

public class s_7964 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int test = sc.nextInt();
		
		for(int t = 1; t <= test; t++) {
			int n = sc.nextInt();
			int m = sc.nextInt();
			int[] a = new int[n];
			int cnt = 0;
			int idx = 0;
			
			for(int i = 0; i < n; i++) {
				a[i] = sc.nextInt();
				if(a[i] == 1)
					idx = i;
			}
			
			int go = m - 1;
			for(int i = idx; i >= 0; i--) {
				if(a[i] == 1) {
					go = m - 1;
				}
				else if(go == 0) {
					a[i] = 1;
					cnt++;
					go = m -1;
				}
				else {
					go--;
				}
			}
			
			for(int i = idx; i < n; i++) {
				if(a[i] == 1) {
					go = m - 1;
				}
				else if(go == 0) {
					a[i] = 1;
					cnt++;
					go = m - 1;
				}
				else {
					go--;
				}
			}
			System.out.println("#" + t + " " + cnt);
		}
	}
}

 

출처

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWuSgKpqmooDFASy&categoryId=AWuSgKpqmooDFASy&categoryType=CODE

SW Expert Academy