종이 조각 풀이

문제 링크: https://www.acmicpc.net/problem/14391

백준 알고리즘 기초 2/2 540에서 4번째 - 14391번 종이 조각을 풀어보았다.

 

풀이: 비트마스크를 이용해 푸는 문제이다.

https://velog.io/@imnotmoon/Python-%EB%B0%B1%EC%A4%80-14391.-%EC%A2%85%EC%9D%B4-%EC%A1%B0%EA%B0%81 를 참고했다.

 

C++

 

Python

n,m=map(int,input().split())
inp=[list(map(int,input())) for i in range(n)]
def sol():
	res=0
	for i in range(1<<n*m):
		total=0
		for row in range(n):
			srow=0
			for col in range(m):
				idx=row*m+col
				if i&(1<<idx)!=0: srow=srow*10+inp[row][col]
				else:
					total+=srow
					srow=0
			total+=srow
		for col in range(m):
			scol=0
			for row in range(n):
				idx=row*m+col
				if i&(1<<idx)==0: scol=scol*10+inp[row][col]
				else:
					total+=scol
					scol=0
			total+=scol
		res=max(res,total)
	return res
print(sol())

Java