본문 바로가기
알고리즘/완전탐색

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

by 임짠짠 2022. 7. 27.
반응형
 

16951번: 블록 놀이

욱제는 높이가 1인 블록을 매우 많이 가지고 있고, 블록을 쌓아서 탑 N개를 만들었다. 탑은 일렬로 배열했고, 왼쪽에서부터 i번째 탑의 높이는 Ai이다. 욱제가 가장 좋아하는 정수는 K이다. 따라서

www.acmicpc.net

 

코드

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 값을 갱신시켜줬다.

반응형

댓글