[BOJ 16951] 블록 놀이 (Java)

BOJ 16951 블록 놀이

문제풀이

한참을 고민하다 제한사항이 다음과 같이 작아서 완전탐색을 시도해보면 되겠다고 생각했다.

• 1 <= N, K <= 1000
• 1 <= A[i] <= 1000

하지만, 완전탐색을 어떻게 할 것인가에서 막혔는데 내가 생각한 것은 블록을 선택해서 그 블록을 감소 또는 증가시키는 모든 경우의 수를 해보는 것이다. DFS로 구현을 해보았지만 시간초과... 애초에 로직도 잘못된 것 같다.

도움을 요청하여 풀이를 들어보니

• 배열은 반드시 오름차순이다.

라는 성질을 이용하여 1000 이하의 수들로 K의 등차를 가지는 모든 등차수열을 구하여 원본 배열과 다른 블록의 수를 세어서 최솟값을 찾으면 된다.

이렇게 간단한걸 왜 생각을 못했을까 실력이 퇴보하는 느낌이다. 더 분발하자!

구현코드

import java.io.IOException;
import java.util.Scanner;

public class Main {
	
	static int N, K, ans;
	static int[] numbers;
	
	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt();
		K = sc.nextInt();
		ans = N;
		
		numbers = new int[N];
		
		for(int i = 0 ; i < N ; ++i) numbers[i] = sc.nextInt();

		for(int i = 1 ; i <= 1000 ; ++i) {
			int time = 0;
			for(int j = 0 ; j < N ; ++j) {
				if(i + j * K != numbers[j]) time++;
			}
			ans = ans > time ? time : ans;
		}
		
		System.out.println(ans);
	}
}