글 읽기 - 반례모음집 다 통과하는데도 50%를 뚫지 못하고 있습니다..

rosf73 2년 전 0

field 상하좌우를 -1로 더 채운 뒤

2칸앞, 1칸앞 비교 dp로 만들었습니다

머리로 짜낼 수 있는 반례는 다 통과하네요....

반례 부탁드려도 괜찮을까요 ㅠㅠ

import sys; s=sys.stdin.readline

for _ in range(int(s())):
	n,m = map(int, s().split())
	field = [[-1]*(m+2) for _ in range(n+2)]
	for i in range(1, n+1):
		j = 1
		for e in list(s().strip()):
			if e == 'x':
				field[i][j] = 1
			else:
				field[i][j] = 0
			j += 1
		
	dp = [0]*20
	# now : idx 라인 최대치 + (idx-1) 라인 가능치
	# pre : idx 라인 가능치 + (idx-1) 라인 최대치
	# 두 경우 비교하여 더 큰 것을 return
	def count_and_select(idx): 
		now_total = dp[idx-2]
		pre_total = dp[idx-1]
		for i in range(1, n+1):
			# 가능치 라인 좌우 상중하 체크
			if field[i][idx] == 0:
				now_total += 1
			
			check = [field[i-1][idx-2], field[i][idx-2], field[i+1][idx-2], field[i-1][idx], field[i][idx], field[i+1][idx]] # now
			if 0 not in check and field[i][idx-1] == 0:
				now_total += 1
				
			check = [field[i-1][idx-1], field[i][idx-1], field[i+1][idx-1]] # pre
			if 0 not in check and field[i][idx] == 0:
				pre_total += 1
		return max(now_total, pre_total)
	
	cnt = 0
	for i in range(1, n+1):
		if field[i][1] == 0:
			cnt += 1
	dp[1] = cnt
	for i in range(2, m+1):
		dp[i] = count_and_select(i)
	
	print(dp[m])

samgkgkgk 2년 전 0

저도 딱 50퍼에서 틀렸었는데, 혹시 저처럼 세로가 1인 경우를 놓친게 아닐까요?

rosf73 1년 전 0

사이즈 1:1 , 1:10 , 10:1 , 10:10

모두 x거나 모두 .거나 이 경우, 저 경우 다 해봤는데도 통과하네요.. 으으 답변은 감사합니다..!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

반례모음집 다 통과하는데도 50%를 뚫지 못하고 있습니다..

rosf73 2년 전 0

samgkgkgk 2년 전 0

rosf73 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말