[백준][Python] 16951번 블록 놀이

16951번: 블록 놀이

 

코드

def check(i):
	cnt = 0
	for a in range(n):
		if a < i:
			if n_list[a] != (n_list[i] - (i-a)*k):
				cnt += 1
		elif a > i:
			if n_list[a] != (n_list[i] + (a-i)*k):
				cnt += 1
	return cnt

n,k = map(int,input().split())
n_list = list(map(int,input().split()))
min_cnt = 1001
for i in range(n):
	if n_list[i] > i*k:
		count = check(i)
		min_cnt = min(min_cnt,count)

print(min_cnt)

 

설명

주어진 탑의 높이 중 하나의 인덱스를 기준으로 삼아 k 만큼 차이가 나게 만들어봤다.

k 만큼 차이가 나게 만들려면 기준이 되는 인덱스의 크기가 (인덱스 번호) * k 보다 커야 가능하다.

위 조건을 만족하는 경우 check 함수에서 총 걸리는 시간을 구했다. 

 

인덱스 번호(a)가 기준이 되는 인덱스(i)보다 작은 경우 n_list[i] - (i-a)*k 와 n_list[a] 값이 같은지 비교해서 다르면 cnt를 1 증가시켰다.

반대로 인덱스 번호가 더 큰 경우 n_list[i] + (a-i)*k 와 n_list[a] 값이 같은지 비교해서 다르면 cnt를 1 증가시켰다.

 

위에서 구한 cnt 값이 기존의 최솟값보다 작은 경우 min_cnt 값을 갱신시켜줬다.