https://www.acmicpc.net/problem/14391
14391번: 종이 조각
영선이는 숫자가 쓰여 있는 직사각형 종이를 가지고 있다. 종이는 1×1 크기의 정사각형 칸으로 나누어져 있고, 숫자는 각 칸에 하나씩 쓰여 있다. 행은 위에서부터 아래까지 번호가 매겨져 있고,
www.acmicpc.net
n, m = map(int, input().rstrip().split())
a = [list(map(int, input())) for _ in range(n)]
ans = 0
for s in range(1 << (n * m)): # n * m 사이즈의 비트마스크
sum = 0
for i in range(n):
cur = 0
for j in range(m):
k = i * m + j # row major order
if (s & (1 << k)) == 0: # 가로일 경우
cur = cur * 10 + a[i][j]
else:
sum += cur
cur = 0
sum += cur
for j in range(m):
cur = 0
for i in range(n):
k = i * m + j
if (s & (1 << k)) != 0: # 세로일 경우
cur = cur * 10 + a[i][j]
else:
sum += cur
cur = 0
sum += cur
ans = max(ans, sum)
print(ans)
- 가로 조각과 세로 조각 두가지로 나뉨
- o과 1로 나누어진 NM개의 칸으로 생각 (max 16개)
- 4X4 공간을 1차원으로 이어붙여 생각 (max 16칸, 16자리 비트로 표현)
1. 비트마스크를 이용해 모든 경우를 구하고
2. 수의 합을 구해주면 된다
-A[I][J] -> i*m+j (row major order)
비트 마스크에 대해 오늘 공부하기 시작했는데,
문제에서는 뭐 배열의 최대 값을 구하라는데 2^n -1 을 왜 차곡차곡넣고있지? 라고 생각했었다.
비트 값으로 연산을 하자는게 아니라
비트를 통해 현재 상태를? 구분짓자는 내용이라는걸 깨달은 순간 문제가 보이기 시작했다.
'백준 알고리즘 (Baekjoon Algorithm)' 카테고리의 다른 글
| [파이썬] 백준 알고리즘 No.1149 RGB 거리 (0) | 2022.01.14 |
|---|---|
| [파이썬] 백준 알고리즘 No.2225 합분해 (0) | 2022.01.13 |
| [파이썬] 백준 알고리즘 No.10819 차이를 최대로 (0) | 2022.01.08 |
| [파이썬] 백준 알고리즘 No.16953 A -> B (0) | 2022.01.07 |
| [파이썬] 백준 알고리즘 No.1248 맞춰봐 (0) | 2022.01.05 |