[프로그래머스] 양궁대회 - python

문제 출처

https://school.programmers.co.kr/learn/courses/30/lessons/92342

프로그래머스

 

 

 

---

문제 풀이

알고리즘 문제는 풀어도 풀어도 어렵다. 꾸준히 문제 푸는 습관을 들여야 하는데 이게 참 어렵다.

 

필자는 처음에 knapsack을 이용해서 해결하고자 했다. 하지만 knapsack을 이용해 구하고자 쉽지 않았다. 먼저 knapsack은 기본적으로 제한된 cost내에서 최고의 value를 구하는 알고리즘이다. 따라서 10개의 화살을 이용해 최대 점수를 구한다고만 생각했고 충분히 구현 가능할 것이라고 생각했다. 모두 구현하고서 깨달았지만 해당 문제는 라이언의 최대 점수를 구하는 것이 아니라, 라이언과 어피치의 점수차이를 최대로 벌리는 것이다. 따라서 해당 방식을 이용해서 접근하자니 오랜 시간이 걸렸고 보다 복잡해졌다.

 

두번째로 생각한 방식은 모든 경우를 체크해보는 것이었다. 아마 itertool의 combinations_with_replacement를 사용해서 구현해볼까 하는 생각이 들었다. 하지만 이 경우에는 시간 복잡도가 꽤 높게 나올 것이다. 라이언과 어피치의 값의 차이를 최대로 만들기 위해서는 특정 점수 과녁을 어피치보다 많이 쏘거나, 아예 포기 하고 다른 과녁를 노려야한다. 하지만 중복 조합의 경우는 어피치가 쏜 곳에 작은 개수의 화살을 쏘는 경우도 포함되기에 무의미한 값들이 들어가는 경우가 많아진다. 따라서 비효율 적이라고 생각했다.

 

따라서 어떤 점수 과녁을 맞춰야 할지에 대한 목표가 있어야 한다. 목표로 하는 과녁은 어피치보다 1발 더 많이 쏘는 것이 좋다. 따라서 10짜리 어레이를 만들고 그 안에 0, 1을 통해 맞출 목표 과녁을 체크하면 된다. 하지만 필자는 비트 마스킹을 사용했다. 10개의 점수 과녁이 있기에 2^10 즉 1024개의 경우가 존재하며 해당 경우마다 10개 점수판을 모두 확인해야하기에 대략 10000 정도의 시간 복잡도가 필요로 한다.

 

 

	def solution(n, info):
	# lian이 최대의 양궁 점수를 얻기 위해서는, 특정 점수 과녁을 어피치보다 많이 쏘거나, 아예 포기 하고 다른 과녁를 노려야한다.
	# 즉 1 ~ 10중에 어떤 과녁을 포기할고, 어떤 과녁을 많이 맞춰야하는 지에 대한 목표가 있어야 한다.
	# 따라서 10짜리 어레이를 만들고 그 안에 0, 1을 통해 맞출 목표 과녁을 체크해도 되지만 비트 마스킹을 사용했다.
	# 10개의 점수가 있기에 2^10 즉 1024개의 경우에 대해 각각의 과녁을 확인해야하기에 대략 10000 정도의 시간 복잡도가 필요로한다.
	# 현재 어피치 점수 체크
	apeach = 0
	for i, v in enumerate(info):
	if v > 0:
	apeach += 10 - i
	M = 0
	answer = [0 for _ in range(11)]
	for goal in range(1, 1 << 11):
	_apeach = apeach
	lian = 0
	cnt = 0
	for i in range(11):
	# goal에 이기고 싶은 과녁 점수들을 체크해놓는다.
	if goal & (1 << i):
	# 라이언이 해당 과녁 점수을 얻는다.
	cnt += (info[10-i] + 1)
	lian += i
	# 어피치가 과녁에 쏜 값이라면 apeach 점수에서 마이너스
	if info[10-i] > 0:
	_apeach -= i
	# 라이언에게 할당된 화살을 초과했다면 다음 목표로
	if n < cnt:
	continue
	# 해당 점수차가 존재한다면, 작은 과녁을 맞춘 goal을 answer로
	if M == lian - _apeach:
	for i in range(11):
	if goal & (1 << i) and (answer[10-i] == 0):
	M = 0
	elif (goal & (1 << i)) == 0 and answer[10-i]:
	break
	# 점수차 큰걸로 업데이트
	if M < lian - _apeach:
	M = lian - _apeach
	answer = [0 for _ in range(11)]
	for i in range(11):
	if goal & (1 << i):
	answer[10-i] = info[10-i] + 1
	# 라이언이 이길수 없다면 [-1]
	if M == 0:
	return [-1]
	# n개를 채우지 않았다면 0점에 화살 추가
	if sum(answer) < n:
	answer[-1] += n-sum(answer)
	return answer

view raw archery_competition.py hosted with ❤ by GitHub