[Python] 백준 17281. ⚾

https://www.acmicpc.net/problem/17281

17281번: ⚾

 

 

삼성A형 기출문제였고, 효율성을 고려하면 백준 환경에서 python 3으로는 사실상 풀 수 없는 문제.

 

1번 타자는 정해져 있고, 나머지 8명의 타자에게 타순을 부여하는 문제이므로

완전탐색이고, 총 탐색해야 할 가짓수는 8!으로 약 4만 개 정도다.

 

python3 설정으로는 시간초과를 절대 해결할 수 없었고, pypy3을 써도 정말 간신히 통과한다.

정말 어떻게 풀어도 시간초과가 해결이 안 나서, 검색으로 찾은 C++ 코드로 통과한 다음 pypy3 통과자들의 코드를 봤는데,

 

변수 할당 하나 때문에 91%에서 시간초과가 계속 났던 거였다.

 

원래는 base를 의미하는 b1, b2, b3도 배열로 선언한 다음 for문으로 체크하도록 코드를 짰었는데,

이 정도로 빡빡한 조건에서는 사치였다.

 

 

	import sys
	from itertools import permutations
	end = int(sys.stdin.readline())
	inning = [list(map(int, sys.stdin.readline().split())) for _ in range(end)]
	max_score = 0
	def game(line_ups):
	hitter_idx = 0
	score = 0
	for each_inning in inning:
	outcount = 0
	b1, b2, b3 = 0, 0, 0
	while outcount < 3:
	# 이 변수 할당 하나가 시간초과를 만들었다.
	# hit_type = each_inning[line_ups[hitter_idx]]
	if each_inning[line_ups[hitter_idx]] == 0:
	outcount += 1
	elif each_inning[line_ups[hitter_idx]] == 1:
	score += b3
	b1, b2, b3 = 1, b1, b2
	elif each_inning[line_ups[hitter_idx]] == 2:
	score += (b2 + b3)
	b1, b2, b3 = 0, 1, b1
	elif each_inning[line_ups[hitter_idx]] == 3:
	score += (b2 + b3 + b1)
	b1, b2, b3 = 0, 0, 1
	elif each_inning[line_ups[hitter_idx]] == 4:
	score += (1 + b1 + b2 + b3)
	b1, b2, b3 = 0, 0, 0
	hitter_idx = (hitter_idx + 1) % 9
	return score
	for line_ups in permutations(range(1,9), 8):
	line_ups = list(line_ups[:3]) + [0] + list(line_ups[3:])
	max_score = max(max_score, game(line_ups))
	print(max_score)

view raw [백준] ⚾.py hosted with ❤ by GitHub